When you connect to a server via SSH the server’s “fingerprint” is saved on your file. You will see this warning if the fingerprint for the server is different than the last time you connected to it. As the warning states, this could be a sign of a “man-in-the-middle attack.”

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
3a:8a:9f:f2:ae:b3:dd:2c:55:6b:46:f5:30:ff:d6:b1.
Please contact your system administrator.
Add correct host key in /home/foo/.ssh/known_hosts to get rid of this message.
Offending RSA key in /home/foo/.ssh/known_hosts:120
  remove with: ssh-keygen -f "/home/foo/.ssh/known_hosts" -R your.ip.address
RSA host key for 107.170.102.240 has changed and you have requested strict checking.
Host key verification failed.

The server is identified by its IP address. So if you create a droplet, destroy it, and create a second one that has the same IP address, you will see this warning. In this case, you can safely ignore it. To remove the warning and connect to the new server, run:

ssh-keygen -f "~/.ssh/known_hosts" -R YOUR.IP.ADDRESS
ssh root@YOUR.IP.ADDRESS

The same problem not that I create one ssh key to my root user on server and also restarted the ssh and sshd service. Now I’m not access my droplet.

$ ssh root@xxx.xxx.xxx.xxx
The authenticity of host ‘xxx.xxx.xxx.xxx (xxx.xxx.xxx.xxx)’ can’t be established.
ECDSA key fingerprint is 59:95:7b:f1:06:3d:51:b2:27:1a:98:fc:0c:47:ac:ec.
Are you sure you want to continue connecting (yes/no)?
Host key verification failed.

Hi, If it helps, after trying to add the new IP address when I changed my drolplet, and not achieve to connect, I just clear ( remove the lines ) the old keys on known_hosts file, and I tried to access again. It generated a new key in this file, it asked me the password, and I could access again. Have Luck!