I am not entirely certain what the cause of this error is but it is particularly annoying when it happens on a headless system.
I think that the problem is caused by too many keys to choose from during key negotiation, or no key at all. I found this workaround.
ssh -o PubkeyAuthentication=no vince@host
Once a successful login with a password is possible, logout and copy the authentication key to the host…
ssh-copy-id -o PubkeyAuthentication=no vince@host
Then login with ssh again…
ssh vince@host
And ssh should authenticate without using a password.
If not, check the permissions on the destination’s .ssh directory and authorized_keys file
vince@host:~ %
chmod 700 .ssh
chmod 600 .ssh/authorized_keys
chown -R vince:vince .ssh