This happens if you have multiple SSH keys loaded into your agent.

Lets say your key file is idrsa and idrsa.pub respectivly

ssh -i ~/.ssh/id_rsa root@111.11.11.111

If you don’t want to type the -i aspect each time create a file in your .ssh folder named config and add an entry like below

Host whatever_name
    HostName 111.11.11.111 or domain.com
    User root
    PreferredAuthentications publickey
    IdentityFile /path/to/.ssh/key_file
    UseKeychain yes
    AddKeysToAgent yes

update the entry to match your setup.

You get that error message when :
PasswordAuthentication no in /etc/sshd_config.

I changed it to “yes”, ran ‘service ssh restart’ and all was well.
Changed it back to “no” and again ran 'service ssh restart’.
ssh to DO machine now works as intended.

NB:I don’t allow password logins.