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.