Why the warning appears
When a machine is reinstalled or an SSH service is rebuilt, its host key changes. Your local ~/.ssh/known_hosts still holds the old key, so the next login fails with:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Remove the stale key
Use ssh-keygen -R to drop the outdated entry for the host (IP or DNS name):
ssh-keygen -R HOST_IP
This edits ~/.ssh/known_hosts in place and works even if entries are hashed (the default on most systems).
Re-add the new key safely
If possible, verify the new host key fingerprint out-of-band (console, cloud UI, or provider metadata).
Connect again so SSH stores the fresh key:
ssh user@HOST_IPConfirm the fingerprint matches what you validated, then accept.
Tips and variants
For hostnames: ssh-keygen -R example.internal.
If multiple entries exist (old IPs, IPv6), ssh-keygen -R removes them all.
After cleaning, a scripted reconnect can proceed without prompts:
ssh -o StrictHostKeyChecking=accept-new user@HOST_IP
Keep the check in place—only remove a key after you are sure the host was legitimately rebuilt. Otherwise, the warning may be protecting you from a real man-in-the-middle attack.