Host key verification failed — and WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED

Quick fix: the server’s host key no longer matches the one your computer saved in ~/.ssh/known_hosts. If you reinstalled or rebuilt the server, or its IP address now belongs to a new machine, check the new fingerprint on the server’s console, then run ssh-keygen -R 203.0.113.10 and connect again. If nothing changed on your side, stop and find out why before you accept the new key.

The full warning, as OpenSSH prints it:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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:xRjk9isUVT5Q/lCDaIaJ3VdsIiZn4C4UWrdU3lMuKMg.
Please contact your system administrator.
Add correct host key in /home/you/.ssh/known_hosts to get rid of this message.
Offending ECDSA key in /home/you/.ssh/known_hosts:3
  remove with:
  ssh-keygen -f "/home/you/.ssh/known_hosts" -R "203.0.113.10"
Host key for 203.0.113.10 has changed and you have requested strict checking.
Host key verification failed.

What does REMOTE HOST IDENTIFICATION HAS CHANGED mean?

Every SSH server has its own host keys, usually one pair each of ED25519, ECDSA and RSA, created when the system is installed or, on cloud images, at first boot. Clients trust them on first use: the first time you connect, SSH shows the key’s fingerprint and asks whether to continue. Answer yes and the public key is written to ~/.ssh/known_hosts. On every later connection the client compares the key the server presents with the saved one. If they differ, it refuses, because a different key is exactly what a man-in-the-middle would present.

Three lines of the warning carry what you need:

• The fingerprint for the … key sent by the remote host — the key the server presents now. This is the one you verify.
• Offending ECDSA key in …/known_hosts:3 — the old entry sits on line 3 of that file. Its type can differ from the new key’s (an ECDSA key saved, an ED25519 key sent); the fix is the same either way.
• remove with: — the exact command that deletes the old entry, already filled in with your file and host.

Did the server really change?

Usually yes, and for a boring reason. The common legitimate causes:

• The OS was reinstalled or the server rebuilt. A fresh system generates fresh host keys.
• The IP address was reused. You deleted a server and the new one got an address you had connected to before, or an address that used to belong to somebody else’s machine is now yours.
• DNS points somewhere else. You moved a domain to a new server, so ssh example.com now reaches a different machine than the one saved under that name.
• Several machines share one name or address. A load balancer, a failover pair or a floating IP can land you on hosts with different keys.
• Someone regenerated the keys. An administrator, or an imaging tool, replaced them on purpose.

If none of these applies — nobody touched the server, and the warning appears on a hotel or café network but not from home — treat it as hostile until you have checked. Do not log in through that connection in the meantime.

How do I check the new fingerprint is genuine?

Compare it with what the server itself reports, read through a channel that does not depend on the SSH connection you are verifying: your provider’s web or VNC console, or a colleague already logged in on the machine.

for f in /etc/ssh/ssh_host_*_key.pub; do ssh-keygen -lf "$f"; done

# 256 SHA256:xRjk9isUVT5Q/lCDaIaJ3VdsIiZn4C4UWrdU3lMuKMg root@server (ED25519)
# 256 SHA256:...  root@server (ECDSA)
# 3072 SHA256:... root@server (RSA)

Take the line with the same key type as the warning (ED25519 in the example) and compare the SHA256: string character for character. If they match, the change is genuine. If someone gives you an older MD5 fingerprint in the aa:bb:cc:… format, print that format with ssh-keygen -E md5 -lf.

How do I remove the old key from known_hosts?

ssh-keygen -R 203.0.113.10
ssh-keygen -R server.example.com          # if you also connect by name
ssh-keygen -R '[203.0.113.10]:2222'       # SSH on a non-standard port

ssh-keygen -R deletes every key stored for that host and keeps the previous file as known_hosts.old. The IP address and each hostname you use are separate entries, so remove all of them. A server on another port is stored as [address]:port; quote that form so the shell leaves the brackets alone.

Then connect again. You get the first-connection prompt, this time with a fingerprint you have already checked. Instead of yes you can paste the fingerprint itself, and SSH compares it for you:

ssh root@203.0.113.10
# The authenticity of host '203.0.113.10 (203.0.113.10)' can't be established.
# ED25519 key fingerprint is SHA256:xRjk9isUVT5Q/lCDaIaJ3VdsIiZn4C4UWrdU3lMuKMg.
# This key is not known by any other names.
# Are you sure you want to continue connecting (yes/no/[fingerprint])?

Why does grep not find the host in known_hosts?

Debian and Ubuntu ship HashKnownHosts yes in /etc/ssh/ssh_config, so entries are stored as |1|… hashes instead of readable hostnames, and grep 203.0.113.10 ~/.ssh/known_hosts finds nothing. ssh-keygen hashes the name before it looks, so -F (find) and -R (remove) still work:

ssh-keygen -F 203.0.113.10
# # Host 203.0.113.10 found: line 3
# |1|Vm/vS7jmqLbl48bq/cm76JIEJhg=|lTt768UJpcYMkjbDCfLeybMhiBw= ssh-ed25519 AAAA...

You can also delete the line the warning named: sed -i '3d' ~/.ssh/known_hosts on Linux, or sed -i '' '3d' ~/.ssh/known_hosts on macOS.

What about Windows and PuTTY?

Windows 10 and 11 ship the same OpenSSH client. The file is %USERPROFILE%\.ssh\known_hosts, and ssh-keygen -R 203.0.113.10 works in PowerShell exactly as above. PuTTY keeps its own list in the registry and shows a WARNING - POTENTIAL SECURITY BREACH! dialog instead. Check the fingerprint it displays the same way, then accept the new key in that dialog.

Why do git and CI fail with Host key verification failed?

A non-interactive session cannot answer the yes/no question, so a host that is not in known_hosts yet fails with a single line. In git it looks like this:

Host key verification failed.
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

Nothing changed here; the host was simply never trusted. Add its key before git runs, and check it against the fingerprints the service publishes. GitHub lists them in its documentation:

ssh-keyscan -t ed25519 github.com > github.key
ssh-keygen -lf github.key            # compare with the published SHA256 fingerprint
cat github.key >> ~/.ssh/known_hosts

In a pipeline, store that verified known_hosts line as a CI variable and write it to the file at the start of the job, rather than scanning on every run: a scan inside the job trusts whatever answers at that moment.

Where you cannot pin keys in advance — provisioning servers that did not exist a minute ago, for instance — StrictHostKeyChecking accept-new is the safe middle ground. It saves the key of a host it has never seen, but still refuses a key that has changed:

# for one command
GIT_SSH_COMMAND='ssh -o StrictHostKeyChecking=accept-new' git clone git@github.com:org/repo.git

# or per host, in ~/.ssh/config
Host *.internal.example.com
    StrictHostKeyChecking accept-new

Pinned keys are not set-and-forget, either. GitHub replaced its RSA host key in March 2023 after the private key was briefly exposed in a public repository — a legitimate change that triggered this exact warning for many users. The fix was to remove the old entry and add the newly published key.

Why does it work as me but fail with sudo?

known_hosts is per user. sudo git pull or sudo ssh runs as root and reads /root/.ssh/known_hosts, which has either never seen the host or still holds the old key you already removed from your own file. Fix the file of the account that actually connects, or better, stop running git as root:

sudo ssh-keygen -f /root/.ssh/known_hosts -R 203.0.113.10

Service accounts such as a deploy user or a CI runner each have their own file too. For keys that every account on a machine should trust, use the system-wide /etc/ssh/ssh_known_hosts.

How do I stop it happening on every rebuild?

Keep the host keys across the reinstall. Back them up while the old system still runs, and restore them on the new one:

# on the old system, before the rebuild
sudo tar czf /root/ssh-host-keys.tgz /etc/ssh/ssh_host_*
# copy the archive somewhere safe, e.g. with scp to your workstation

# on the new system
sudo tar xzf ssh-host-keys.tgz -C /
sudo restorecon -Rv /etc/ssh        # Rocky, Alma and RHEL only (SELinux labels)
sudo systemctl restart ssh          # the unit is called sshd on Rocky, Alma and RHEL

Treat that archive like a password: whoever holds the private host keys can impersonate the server.

For a fleet, SSH certificates remove the problem at the root. You sign each server’s host key with a certificate authority and tell clients to trust the CA once, with a @cert-authority line. A rebuilt server gets a newly signed key, and no client ever warns:

# on the CA machine: sign the server's public host key
ssh-keygen -s host_ca -I web1 -h -n web1.example.com ssh_host_ed25519_key.pub
# copy ssh_host_ed25519_key-cert.pub back into /etc/ssh/ on the server

# /etc/ssh/sshd_config on the server
HostCertificate /etc/ssh/ssh_host_ed25519_key-cert.pub

# ~/.ssh/known_hosts on every client
@cert-authority *.example.com ssh-ed25519 AAAAC3Nza... host-ca

The opposite case comes up too. A server cloned from an image that already contained host keys shares them with every other clone of that image, and you want fresh ones. The next new connection will show the warning, which this time you caused yourself.

sudo rm /etc/ssh/ssh_host_*
sudo dpkg-reconfigure openssh-server    # generates new keys
sudo sshd -t && sudo systemctl restart ssh

sudo rm /etc/ssh/ssh_host_*
sudo ssh-keygen -A                      # generates any missing key types
sudo restorecon -Rv /etc/ssh
sudo sshd -t && sudo systemctl restart sshd

On a VMHeaven VPS, a reinstall from the panel builds a fresh system with fresh host keys, so this warning is expected right after one. Open the VNC console in the panel, read the new fingerprint there with ssh-keygen -lf, and only then remove the old entry. The same console gets you in if SSH stops answering altogether — every KVM plan includes it.

Once the key is accepted, the next errors people hit are different problems: Permission denied (publickey) when the server rejects your key, Too many authentication failures when your agent offers too many keys, and Connection refused when sshd is not listening at all. On a freshly installed server, securing SSH access is the next job.

Frequently asked