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…