Safely Fix SSH Permission Denied and Host Key Changed Errors

SSH errors that look similar can have very different causes. Permission denied (publickey) means authentication failed; REMOTE HOST IDENTIFICATION HAS CHANGED means the server identity stored in known_hosts no longer matches.

Diagnose them separately and verify the host fingerprint before removing any trust record.

Fix Permission denied (publickey)

Start with the exact user, host, port, and key:

ssh -vvv -i ~/.ssh/id_ed25519 -o IdentitiesOnly=yes deploy@203.0.113.10

Verbose output should show which key is offered and whether the server accepts it. Common mistakes include:

• connecting as root while the key belongs to deploy;
• using a different private key than the matching .pub file;
• pointing to the wrong server or SSH port;
• placing the public key in the wrong user’s home directory;
• incorrect ownership or permissions on .ssh and authorized_keys.

On the VPS, check:

chmod 700 ~/.ssh
chmod 600 ~/.ssh/authorized_keys
chown -R "$USER":"$USER" ~/.ssh
sudo journalctl -u ssh --since "10 minutes ago"

The user’s home directory must also be accessible to the SSH daemon. Check /etc/ssh/sshd_config for PubkeyAuthentication, AuthorizedKeysFile, and any AllowUsers or DenyUsers rules. Validate changes with:

sudo sshd -t
sudo systemctl reload ssh

Fix REMOTE HOST IDENTIFICATION HAS CHANGED

This warning can be a legitimate server rebuild or IP reuse, but it can also indicate a man-in-the-middle attack. Verify the new host key fingerprint through your VPS provider console or another trusted channel first.

After verification, remove only the old entry:

ssh-keygen -F 203.0.113.10
ssh-keygen -R 203.0.113.10
ssh-keygen -R '[203.0.113.10]:2222'

Reconnect and compare the displayed fingerprint with the value you verified. Do not “fix” this by setting StrictHostKeyChecking=no globally.

Windows known_hosts location

OpenSSH on Windows normally stores the file at $env:USERPROFILE\.ssh\known_hosts. Use the same ssh-keygen -R command from PowerShell after verifying the new fingerprint.

A safe recovery order

1. Confirm the destination IP and port.
2. Verify the host fingerprint when the warning is about host identity.
3. Test the intended user and private key with verbose output.
4. Check server-side key location and permissions through a console or existing session.
5. Validate and reload SSH configuration.
6. Test a fresh connection before closing the recovery session.

Never delete all known_hosts entries or disable host verification as a first response. Narrow changes preserve useful security signals.