Is it safe to remove a host key from known_hosts?

Only if you know why the key changed (server reinstall, IP reuse). If unexpected, verify with the server admin — it could indicate a MITM attack.

Should I use RSA or Ed25519 keys?

Ed25519 is recommended for new keys: smaller, faster, and more secure. Use: ssh-keygen -t ed25519

Linux SSH Key Errors — Agent Forwarding, Host Key & Permission Denied (publickey)

Warningnetwork

Overview

Fix SSH key errors including 'Permission denied (publickey)', host key verification failed, agent forwarding issues, and key format incompatibilities.

Key Details

'Permission denied (publickey)' means the server rejected all offered keys
Host key verification failed: server's host key changed (possible MITM or server reinstall)
SSH keys must have strict permissions: private key 600, .ssh dir 700
ssh-agent stores decrypted keys in memory for convenient reuse
Agent forwarding (-A) allows using local keys on remote servers but has security implications

Common Causes

Public key not in ~/.ssh/authorized_keys on the server
Wrong permissions on private key file (must be 600 or more restrictive)
SSH server configured to reject the key type (e.g., RSA disabled, only Ed25519 accepted)
Wrong user: trying to SSH as user A but key is authorized for user B
Server host key changed: legitimate (reinstall) or suspicious (MITM)

Steps

1Debug connection: ssh -vvv user@host to see which keys are offered and rejected
2Fix key permissions: chmod 600 ~/.ssh/id_rsa && chmod 700 ~/.ssh
3Copy key to server: ssh-copy-id user@host (adds your public key to authorized_keys)
4For host key change: ssh-keygen -R hostname (removes old host key from known_hosts)
5Check sshd config: cat /etc/ssh/sshd_config — look for PubkeyAuthentication and AuthorizedKeysFile