WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!

ssh prints WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! and refuses to connect when the key the server presents does not match the one stored for that host in ~/.ssh/known_hosts. Usually the server was rebuilt and has new host keys; it can also be an interception attack. Check the new fingerprint through another channel, then delete the stale entry with ssh-keygen -R HOST and connect again.

What the message looks like

The full output of OpenSSH (the fingerprint, user name and line number vary):

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 ED25519 key sent by the remote host is
SHA256:<fingerprint>.
Please contact your system administrator.
Add correct host key in /home/user/.ssh/known_hosts to get rid of this message.
Offending ED25519 key in /home/user/.ssh/known_hosts:3
Host key for server.example.com has changed and you have requested strict checking.
Host key verification failed.

The Offending ... key in FILE:N line tells you which line of known_hosts holds the old key.

Fix: remove the old key

ssh-keygen -R deletes every key stored for a host (hashed entries included) and keeps a backup as known_hosts.old. Here on a demo known_hosts file with -f; without -f it edits ~/.ssh/known_hosts:

ssh-keygen -q -t ed25519 -N '' -C old -f oldkey
echo "server.example.com $(cut -d' ' -f1,2 oldkey.pub)" > known_hosts
echo "other.example.com $(cut -d' ' -f1,2 oldkey.pub)" >> known_hosts
ssh-keygen -F server.example.com -f known_hosts | head -1
ssh-keygen -R server.example.com -f known_hosts
cut -d' ' -f1 known_hosts

# Host server.example.com found: line 1
# Host server.example.com found: line 1
known_hosts updated.
Original contents retained as known_hosts.old
other.example.com

Then connect again. ssh shows the new fingerprint and asks Are you sure you want to continue connecting (yes/no/[fingerprint])?; compare it with the fingerprint printed on the server by ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub before you type yes.

If you connect by IP as well as by name, remove both: ssh-keygen -R 203.0.113.10. For a non-standard port the entry is [host]:2222, so run ssh-keygen -R '[server.example.com]:2222'.

Disposable hosts

For test VMs that are rebuilt often, keep their keys out of your main file:

Host *.test.internal
  UserKnownHostsFile ~/.ssh/known_hosts_test
  StrictHostKeyChecking accept-new