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

  1. If possible, verify the new host key fingerprint out-of-band (console, cloud UI, or provider metadata).

  2. Connect again so SSH stores the fresh key:

    ssh user@HOST_IP
    
  3. Confirm 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.