"REMOTE HOST IDENTIFICATION HAS CHANGED" — read this before you delete anything

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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)!
...
Offending ECDSA key in /Users/you/.ssh/known_hosts:14
Host key verification failed.

The first search result for this will tell you to run ssh-keygen -R hostname and move on. That works, and about 95% of the time it is also correct. This guide is about the other 5%, because the whole point of the warning is that you cannot tell which case you are in from the message alone.

What the warning actually says

Every SSH server has a host key — a keypair that identifies the machine, not you. The first time you connect, your client saves the public half in ~/.ssh/known_hosts. That is trust on first use: you accept the identity once, and from then on SSH checks that the server still proves ownership of the same key.

The warning means the key the server presented today does not match the one you recorded. Two things could be true:

• The server legitimately has a new key.
• You are not talking to the server you think you are.

SSH cannot distinguish them, so it refuses to connect and hands the decision to you. It is doing its job — this is the one moment the entire host key system exists for.

The harmless reasons, in order of likelihood

The server was rebuilt or reinstalled. New OS install, new VM from a snapshot, container replaced. Host keys are generated at first boot, so a rebuild means a new identity. Overwhelmingly the most common cause.

The IP address was recycled. You connected to 198.51.100.14 last month when it belonged to one VPS; that VPS was destroyed and the provider handed the address to somebody else’s machine. Very common on cloud providers with dynamic pools, and also the case where the warning is genuinely telling you something you want to know.

The server’s keys were regenerated deliberately. Some hardening playbooks rotate host keys; some cloud images regenerate them on first boot precisely so that every instance from that image is not sharing one key.

You are behind a new load balancer or proxy that terminates SSH, and the servers behind it do not share a host key set. This one is worth raising with whoever runs it, because it makes the warning fire at random and trains everybody to ignore it.

The reason that matters

Someone is intercepting the connection: a hostile network, DNS or ARP poisoning, a compromised jump host, an attacker who has taken the address. You would authenticate to their server, and if you use a password, you have just handed it over.

The tell is context, not the message text. Did anything actually happen to this server? If you rebuilt it an hour ago, the mystery is solved. If it has been running untouched for eight months and the key changed while you are on hotel Wi-Fi, do not clear the entry — verify.

Verifying a new fingerprint properly

The only verification that means anything is one that does not travel over the connection you are suspicious of. Get the fingerprint through a different channel:

• The provider’s web console — the serial console or VNC on DigitalOcean, Hetzner, AWS, Vultr. This is the practical answer for a VPS.
• AWS EC2 prints host key fingerprints in the instance’s system log, retrievable via the console or aws ec2 get-console-output.
• Your configuration management — if Ansible or Terraform provisioned the box, the key is probably in your inventory or state.
• A colleague already logged in, over a session that predates the change.

Once you are on the server by some other route, print its fingerprints:

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

And compare with what your client is being offered:

ssh-keyscan -t ed25519 example.com | ssh-keygen -lf -

The two strings must match exactly. If they do, the change is real and you can clear the old entry. If they do not, stop, and treat the network path as hostile.

Clearing the entry, once you have decided

ssh-keygen -R example.com

That removes every entry for that name and works whether or not your known_hosts is hashed — which is why it beats opening the file and deleting line 14 by hand. If you connect by IP as well as by name, remove both:

ssh-keygen -R example.com
ssh-keygen -R 198.51.100.14

Then reconnect. You will get the ordinary first-time prompt, and this time you have a fingerprint to check it against.

If the server runs on a non-standard port, the entry is stored in bracketed form and needs it too:

ssh-keygen -R '[example.com]:2222'

What not to do

StrictHostKeyChecking no turns the warning off permanently and accepts any key from anyone, forever. It converts SSH into a protocol with encryption but no authentication, which is a surprisingly precise description of “vulnerable to a man in the middle”. You will find it recommended in a lot of CI snippets; those snippets are wrong, and the correct answer there is to pin known host keys in the runner image.

Deleting ~/.ssh/known_hosts wholesale because one entry is in the way. You are throwing away the accumulated identity of every server you have ever used to solve a problem with one of them.

Clicking through it in a GUI client without reading which host it names. If you are connecting through a bastion, a changed key on the jump host is a very different problem from a changed key on the target — and it is the one that lets an attacker impersonate everything behind it.

How a GUI client should handle this

A well-behaved client makes the changed-key case a hard stop, not a dialog with a default button. Upshell pins the key on first connection and refuses to proceed on a mismatch; clearing a pin is a deliberate action in the host editor, not something you can dismiss by hitting Return while distracted. When the connection goes through jump hosts, each hop is verified against its own entry and the error names the hop that failed, so “the bastion’s key changed” and “the target’s key changed” never look alike.

The same client also does not auto-reconnect after a host key mismatch. Retrying is exactly the wrong reflex in the one case where the warning is real.

Step by step

1. Read the hostname in the message — and, if you are jumping, which hop it refers to.
2. Ask what changed. Rebuilt, reimaged, migrated, new IP from the provider’s pool? If yes, you have your explanation.
3. If nothing explains it, get the real fingerprint out of band — provider console, cloud system log, config management, a colleague’s existing session.
4. Compare — ssh-keygen -lf /etc/ssh/ssh_host_ed25519_key.pub on the server against ssh-keyscan -t ed25519 <host> | ssh-keygen -lf - from your Mac.
5. Only if they match, clear and reconnect — ssh-keygen -R <host>, plus the IP and the [host]:port form if you use them.

Questions people ask

Is it safe to just run ssh-keygen -R?

It is safe when you know why the key changed. It is not a diagnosis — it deletes the evidence and lets the connection through. Establish the reason first; the command takes two seconds afterwards.

Why did this happen after I rebuilt my VPS?

Host keys are generated on first boot, so a reinstall produces a new server identity. This is the expected, benign case, and clearing the old entry is the right move.

What is the difference between this and “The authenticity of host can’t be established”?

That one is the first connection — you have no record yet, and SSH is asking you to accept one. This one is a mismatch against a record you already have, which is a much stronger signal and why it blocks instead of prompting.

Should I use StrictHostKeyChecking no in CI?

No. Pin the expected host keys into the runner’s known_hosts at image build time, or use ssh-keyscan once and commit the result. Disabling the check makes every CI connection acceptable to any machine that can answer on that address.