There are plenty of discussions around why you might need to enable sshd options if you see this error, but before hacking your config, did you add a new key to a key-only login config with the following type of command:
$ cat >>authorized_keys
[paste text]
[ctrl+d]
$
If so, take a look inside your authorized_keys file and see if the terminal used for pasting has helpfully added newlines into your key…