Fix “REMOTE HOST IDENTIFICATION HAS CHANGED!” Safely (Windows + PowerShell)

When you try to SSH into a server and see:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Host key verification failed.

don’t just delete things blindly. This warning protects you from man-in-the-middle attacks. Here’s a safe, repeatable workflow to fix it properly and prevent it next time.

TL;DR (Safe Workflow)

1. Verify the new fingerprint out-of-band (console/VNC, not via SSH).
2. Remove old entries for that host from your known_hosts.
3. Add the correct new key (accept on first connect, or pre-seed with ssh-keyscan).
4. Reconnect and you’re done.

1) Verify the server’s fingerprint (out-of-band)

Log in to your server console (cloud provider web console / rescue mode / VNC). Then run:

# Show the ED25519 host key fingerprint (SHA256)
ssh-keygen -l -E sha256 -f /etc/ssh/ssh_host_ed25519_key.pub

You’ll see something like:

256 SHA256:Ua0iZJ+****************WBfcl3GAX2Qc root@hostname (ED25519)

Make sure this exactly matches the fingerprint shown in your SSH error on the client. If it doesn’t match, stop and investigate DNS, routing, or proxies before proceeding.

Why ED25519? It’s modern, fast, and the current default for OpenSSH host keys.

2) Remove old known_hosts entries (Windows PowerShell)

Your error message will point to the file and line, e.g.:

Offending ECDSA key in C:\Users\Que\.ssh\known_hosts:6

Clean up both the IP and the domain (do both):

ssh-keygen -R <your-ip-address>
ssh-keygen -R <your-host-name>

Optionally open the file to confirm:

notepad $env:USERPROFILE\.ssh\known_hosts

Delete any remaining lines for that host (IP and domain, any key type), then save.

Have multiple machines (Win/Mac/Linux/WSL)? Repeat this cleanup on each one.

3) Add the correct new key (pick one method)

Method A — Accept on first connect (safest & easiest)

ssh -o StrictHostKeyChecking=accept-new root@<your-ip-address>

Check the fingerprint shown matches what you verified in step 1, then type yes. The correct ED25519 key is stored in known_hosts.

Method B — Pre-seed with ssh-keyscan (good for automation/CI)

After you’ve verified the fingerprint out-of-band:

ssh-keyscan -t ed25519 <your-ip-address> | Out-File -Append -Encoding ascii $env:USERPROFILE\.ssh\known_hosts
ssh-keyscan -t ed25519 <your-host-name> | Out-File -Append -Encoding ascii $env:USERPROFILE\.ssh\known_hosts

Note: ssh-keyscan doesn’t verify authenticity by itself—that’s why step 1 is mandatory.

4) Reconnect

ssh root@<your-ip-address>
# or
ssh root@<your-host-name>

No more “host identification has changed” errors if everything is correct.

Why this happens

• You reinstalled the OS or regenerated OpenSSH host keys.
• You switched images or restored from a snapshot with different keys.
• The host changed IP/record or you used both IP and domain previously.
• You once connected to a different host at the same IP/domain.

Prevent it next time

1. Persist host keys across rebuilds
   Back up /etc/ssh/ssh_host_* (securely) and restore after reinstall.
2. Standardize on ED25519
   Avoid mixed legacy types (ECDSA/RSA) unless required.
3. Publish SSHFP DNS records (optional, advanced)
   Lets clients verify host keys via DNSSEC-protected records.
4. Document & announce new fingerprints
   If you operate a team or CI, post the new fingerprint before cutovers.

Troubleshooting

• Different networks / proxies in the middle?
  Re-verify the fingerprint from the server console, not via SSH. Test from a clean network (e.g., mobile hotspot).
• You used both IP and domain previously?
  Remove both entries. They’re stored separately.

Still seeing the error?
Run both removals again:

ssh-keygen -R <your-ip-address>
ssh-keygen -R <your-host-name>

Then open C:\Users\<you>\.ssh\known_hosts and manually confirm there’s no leftover line.

Bonus: One-shot PowerShell fixer (safe version)

Assumes you’ve already verified the correct fingerprint out-of-band.

# Params
$HostIP   = "<your-ip-address>"
$HostName = "<your-host-name>"

# 1) Remove old known_hosts entries
ssh-keygen -R $HostIP   | Out-Null
ssh-keygen -R $HostName | Out-Null

# 2) Pre-seed ED25519 keys (optional if you prefer accept-new)
$known = "$env:USERPROFILE\.ssh\known_hosts"
ssh-keyscan -t ed25519 $HostIP   | Out-File -Append -Encoding ascii $known
ssh-keyscan -t ed25519 $HostName | Out-File -Append -Encoding ascii $known

# 3) First connection (prompts once if you didn’t pre-seed)
ssh -o StrictHostKeyChecking=accept-new root@$HostIP

Final checklist

• Fingerprint verified from server console matches exactly
• Old known_hosts entries (IP + domain) removed
• New ED25519 key added (accept-new or pre-seeded)
• SSH connects cleanly without warnings

That’s it—fixed safely and permanently.