WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! means the server answered with a different host key from the one your known_hosts file recorded for that name, and the SSH client refused to connect. If you know why the key changed (the server was rebuilt), remove the old entry with ssh-keygen -R, check the new fingerprint on the server, and only then trust it.

If you do not know why the key changed, stop and ask whoever runs the server. The warning exists for the case where someone else is answering in its place.

The error

$ ssh -o BatchMode=yes dev@sshd hostname
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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:l8KVvx7J8AJG5Ut6/HOBSFEC04QZe0anw7FA7Mlrthk.
Please contact your system administrator.
Add correct host key in /root/.ssh/known_hosts to get rid of this message.
Offending ECDSA key in /root/.ssh/known_hosts:3
  remove with:
  ssh-keygen -f '/root/.ssh/known_hosts' -R 'sshd'
Host key for sshd has changed and you have requested strict checking.
Host key verification failed.
exit=255

Why it happens

The client had connected to sshd once with StrictHostKeyChecking=accept-new, which printed that it added the server's ED25519 key; by the time of the error its known_hosts held three lines for sshd, as ssh-keygen -R reports below. The server container was then removed and a new one started under the same name and network alias, and the new container generated its own host keys. On the next connection the name was the same but the key was not. The old server's Ed25519 fingerprint was SHA256:wCTGTpVE18AzEQK8o3vD8OTTrPOXUrhMtUgGNTQHFe0; the new one is the SHA256:l8KVvx7J8AJG5Ut6... value in the message.

This test reproduced the rebuilt-container case only, and the client stopped with exit code 255. The message itself does not say why the key changed, which is why the fingerprint is compared before the new key is trusted.

The fix

On the client, remove every stored key for the name:

$ ssh-keygen -R sshd
# Host sshd found: line 1
# Host sshd found: line 2
# Host sshd found: line 3
/root/.ssh/known_hosts updated.
Original contents retained as /root/.ssh/known_hosts.old
exit=0

On the server, print the fingerprint of its host key:

$ ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub
256 SHA256:l8KVvx7J8AJG5Ut6/HOBSFEC04QZe0anw7FA7Mlrthk root@0a1f3b7bcdc9 (ED25519)
exit=0

Back on the client, fetch the key, compare its fingerprint, then add it and connect:

$ ssh-keyscan -t ed25519 sshd > /root/sshd.key
# sshd:22 SSH-2.0-OpenSSH_9.6p1 Ubuntu-3ubuntu13.20
exit=0
$ ssh-keygen -lf /root/sshd.key
256 SHA256:l8KVvx7J8AJG5Ut6/HOBSFEC04QZe0anw7FA7Mlrthk sshd (ED25519)
exit=0
$ cat /root/sshd.key >> /root/.ssh/known_hosts
exit=0
$ ssh -o BatchMode=yes dev@sshd hostname
0a1f3b7bcdc9
exit=0

The two fingerprints match, so the key that answered on the network is the one on the server's disk. The comparison is the step that matters: ssh-keyscan stores whatever key answers. Here the server's fingerprint was read with docker exec in the server container, not over SSH; on a real server, read it through a channel you already trust rather than the connection you are checking.

How it was reproduced

Reproduced inside ubuntu:24.04 containers on Docker engine 29.9.3, with OpenSSH_9.6p1 Ubuntu-3ubuntu13.20 as client and server. The client connected once with -o StrictHostKeyChecking=accept-new; then the server container was replaced with docker rm -f and docker run --network-alias sshd, and the new container ran ssh-keygen -A for fresh host keys. The containers were removed afterwards.

Frequently asked

How do I fix WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED?
If you know the server was rebuilt, run ssh-keygen -R with the host name, check the new key's fingerprint on the server with ssh-keygen -lf, compare it with what ssh-keyscan fetches, and add it to known_hosts.
Why does SSH say the host key changed after I recreated a Docker container?
The new container generated new host keys under the same name. The client still held the old key for that name in known_hosts and refused the new one.
Is it safe to delete the known_hosts line for REMOTE HOST IDENTIFICATION HAS CHANGED?
Only when you know why the key changed and you have compared the new fingerprint with the one on the server. Otherwise the warning may be the attack it describes.

For a host that was never in known_hosts, see Host key verification failed. More decoded errors in the Fixes category.