CORE OS Solution:
If using coreos set the username 'core' instead of 'root'.
Once you've logged in you can use 'sudo -i' to become root.
I was having a same problem, I read a few tutorials here in DO and I believe I know what the problem was.
My step was: create a new droplet (brand new account / droplet), not using any key and THEN generate a key after the droplet created.
The problem was, the key was not automatically assigned to the droplet (I read this on one of the tutorials). It is possible to assign the key into an existing droplet (again, read on tutorial) but I didn't use that solution.
My solution: I deleted the key from DO's record, delete the droplet (luckily it was still empty) and then create a new droplet, but this time, using the key since the beginning (when it was asked during droplet's creation, whether we want to use a key or not). Basically just start from scratch, but this time I "rearranged" the steps. I was using the same key, there was a pop up saying that this key already cached but on different droplet (something along that line), hit yes, and everything works.
Just a suggestion, DO should warn the user regarding this issue. Well.. I don't really think that this is an issue / bug, but.. I think it'd be nice to know this since the beginning. For example, on this tutorial:
On this part "Step Seven-Select SSH Keys (Optional)" >> It should be clear that it would take more, extra effort if we choose to create a key later (manually assign it to the droplet).
Again, just a suggestion. HTH
Digital Ocean needs to improve these tutorials. Digital Ocean needs to improve them not their customers. Your customer's follow them only to learn that they lack detail, skip steps, or just plain suck. It leads to a lot of non-value adding activity.
Just check your secure log. In my case (Centos) the file is locate in /var/log/secure.
In my log:
Jan 24 16:52:40 server sshd: Authentication refused: bad ownership or modes for directory /home/user
After I changed the modes /home/user from 0755 to 0700 I can login with the key.
My problem was found in the var/ logs/secuirty apparently, i used a windows text editor that caused a /r switch to be entered into the /bin/bash command when attempting to login. tech support gave me a command to reset it. I will look around to find it.
usermod -s /bin/bash root
I had same problem, tried everything but kept refusing my key, or prompting me for a password in addition to the key.
Turns out i kept accidentally creating a droplet using CoreOS instead of CentOS...not sure what the deal is with CoreOS...but glad i don't need to use that right now or i would be in for trouble or switching to a i different service.
If you just upgraded Ubuntu 15.04/10 to Ubuntu 16.04 LTS (or otherwise upgraded OpenSSH from v6.9 to v7.0 you may be getting the ssh refusal because of changes in OpenSSH.
I was specifically getting this error in the /var/log/auth.log (via Webmin): sshd: userauth_pubkey: key type ssh-dss not in PubkeyAcceptedKeyTypes [preauth].
For this specific error, you need to add "PubkeyAcceptedKeyTypes=+ssh-dss" (without the quotations) to the bottom of your /etc/ssh/sshd_config file.
I had the same problem after following this tutorial : https://www.digitalocean.com/community/tutorials/initial-server-setup-with-ubuntu-14-04
I first thought, I had to use chmod 644 rather than 600 for the authorized_keys file as @Tecca suggests, I tested both now that I solved my problem and it makes no difference to use one or another.
PuTTY Key Generator inserted some sort of "carriage return" in my public SSH key so the copy / paste was incomplete. Maybe others will have the same issue, so I strongly recommend you to double check if your key is complete.