Fresh install of Ubuntu 16.04. SSH error: Permission denied (publickey).

I wanted a fresh start for a project idea. I just rebuilt my droplet with the Ubuntu 16.04.1 x64 image. I received the root password in my email. I wanted to SSH into the server, so I removed the hostname from my known_hosts (in this case, I just deleted my known_hosts file). Every time I attempt to log in I get the message “Permission denied (publickey).”

I’ve tried to do some research on this message, and I don’t understand what I need to do to fix it. I found I can log in to the server using the console on the DO management page, but that console is very laggy. I’d prefer to use my native console. Any pointers?

jfagan@waxball:~/.ssh$ ssh root@mydomain.com
The authenticity of host 'mydomain.com (123.456.789.123)' can't be established.
ECDSA key fingerprint is xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'mydomain.com,123.456.789.123' (ECDSA) to the list of known hosts.
Permission denied (publickey).