Make sure you didn’t changed private key any time after creating Droplet.
If you used one key on Droplet creation, and changed it (even in Control Panel), the original one key will be used.

/* Comment
I guess this is a OK behavior. If you go to Settings -> Security, change existing SSH key it'll generate new key fingerprint. Droplets identify SSH keys by fingerprint, not by name so I guess it's correct.
I will verify this behavior with DigitalOcean and maybe I update this */

To debug this, you can use DigitalOcean Web Console. Login to Control Panel, select your Droplet and click Console on right side.
If you have non-root user, use it in combination with password and you will be able to login.
If you have root user only and don’t have password, you can use Reset Root Password from ‘Access’ option of Droplet details. It’ll be mailed to your password and you can login with it via Console.
Probably you will have to change it on first login, you will be first asked for current password then 2 times for new one.

You can take look at SSH keys tutorial for steps. You will need to copy it manually as ssh-copy-id is not available via Console.
You can temporary enable password authentication. Open SSH config:

sudo nano /etc/ssh/sshd_config

Find out PasswordAuthentication to yes:

PasswordAuthentication yes

Save file and exit editor. It requires you to restart SSH service:

sudo systemctl restart sshd

After this you can use SSH with password to debug. Once public key starts to work, make sure PasswordAuthentication is set to no and restart service to disable password logins.

I had the same problem, and after 4-5 hours I realize the problem and found the solution.

I’m not sure about the reason, but the server only allows keys with 1024 bytes. You can:

1. create a 1024 key locally: ssh-keygen -t rsa -b 1024 -N "" -f ~/.ssh/id_rsa_docean
2. add it to the keys in your profile
3. use it to create the droplet
4. use it to login: ssh root@YOUR_IP -i id_rsa_docean

Because of another bug, maybe using more than 1 key may fail because the authorized_keys may corrupt.

I’d love to know why those two problems: the authorized_keys mess and the size limit in the key.

<^>You can take look at SSH keys tutorial for steps. You will need to copy it manually as ssh-copy-id is not available via Console.
You can temporary enable password authentication. Open SSH config:

sudo nano /etc/ssh/sshd_config

Find out PasswordAuthentication to yes:

PasswordAuthentication yes

Save file and exit editor. It requires you to restart SSH service:

sudo systemctl restart sshd

<^>
This works! Thanks

In my case there was a problem with directory permissions. Check this out

/home

drwxr-xr-x.   9 root root   113 Jun 28 22:57 home

and then your home directory:

drwxr-----   5  user group   124 May 18 17:00 user
drwx------  2  user group   29 May 18 12:05 .ssh
-rw-------  1 user group 2235 Jun 28 23:09 authorized_keys

Troubleshooting

• start sshd in debug mode

service sshd stop

run sshd debug mode:

/usr/sbin/sshd -ddd

my error messages

...
          debug1: trying public key file /home/USER/.ssh/authorized_keys
          debug1: Could not open authorized keys '/home/USER/.ssh/authorized_keys': Permission denied
...