SSH Host Key Verification Failed Error Fix After Server IP Change

SSH's host key warning after a server's IP address changes, or after a genuine reinstall, is the client correctly detecting that the server's identity fingerprint no longer matches what it previously recorded — this is exactly the security check working as intended, and the fix requires confirming the change is legitimate before removing the old, now-mismatched record.

The Problem

Connecting to a server you've legitimately connected to before, after that server's IP changed or the server itself was reinstalled/rebuilt, produces a prominent warning:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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)!
...
Host key verification failed.

Why This Check Exists

Every SSH server has a unique cryptographic host key, and the first time you connect to a server, your SSH client records that key's fingerprint locally (in ~/.ssh/known_hosts). On every subsequent connection, the client compares the server's currently presented key against this recorded fingerprint — a mismatch is exactly what this warning flags, and it's specifically designed to protect against a man-in-the-middle attack, where a malicious actor intercepts your connection and presents their own key while pretending to be the legitimate server you intended to reach. The warning is loud and alarming by design, precisely because ignoring it could mean connecting to and authenticating against an actively malicious party rather than your genuine server.

The Fix

Before removing anything, confirm the key change is actually legitimate and expected — because you know the server's IP genuinely changed, was reinstalled, or its host key was intentionally regenerated, not because you're simply trying to make an alarming warning go away without understanding why it appeared. If you have any doubt about whether this specific change is expected, investigate further (contact whoever manages the server, check recent infrastructure change logs) before proceeding.

Once you've confirmed the change is legitimate, remove the specific outdated entry from your known_hosts file, ideally targeting only the specific affected host rather than clearing the entire file:

ssh-keygen -R old-or-changed-hostname-or-ip

This removes only the entry for the specific host in question, leaving every other server's recorded host key entries untouched and still providing their own protection.

Reconnect, which will prompt you to accept and record the new host key, since this now appears (from the client's perspective) as a genuinely new, previously-unseen server:

ssh user@hostname
The authenticity of host 'hostname' can't be established.
Are you sure you want to continue connecting (yes/no)?

Before typing "yes," ideally verify the presented key fingerprint against a fingerprint you've obtained through a separate, trusted channel (checking your cloud provider's dashboard, which often displays the server's genuine host key fingerprint directly, or asking whoever manages the server to confirm it through a different communication channel) — this is the step that actually provides genuine security assurance here, since simply typing "yes" without any verification effectively reduces this entire mechanism to "trust on first use" without confirming that first use is genuinely trustworthy.

If you manage infrastructure where servers are frequently rebuilt or IPs frequently change as part of normal, expected operations (auto-scaling groups, frequently rebuilt development/staging environments), consider whether disabling strict host key checking specifically for those known, frequently-changing, lower-risk hosts is an appropriate tradeoff — though this should be a deliberate, scoped decision, not a blanket disabling applied to every host including genuinely sensitive production servers:

# ~/.ssh/config - scoped specifically to a known pattern of frequently-changing hosts
Host dev-*.internal.example.com
    StrictHostKeyChecking no
    UserKnownHostsFile /dev/null

Still Not Working?

If the host key keeps changing unexpectedly and repeatedly, even for a server you don't believe should be changing, this pattern itself is worth investigating rather than simply repeating the removal-and-reconnect process each time without further thought — a server's host key changing without an intentional, known reason behind it (no recent reinstall, no infrastructure change you're aware of) could genuinely indicate a security incident, a misconfigured load balancer randomly routing you to different backend servers with different keys, or another underlying infrastructure issue that deserves direct investigation rather than being routinely bypassed.