Do you think they are compromised? Generally you have to invalidate the public keys in any .ssh_hosts file that accepts them, and create new ones instead. I generally install .ssh_hosts on remote machines using an ansible playbook. I don’t have any automation to cycle them but I guess I would also do that with ansible if I thought it were needed.

Ansible may be old school by now, but it works for me. Maybe the cool kids are using something newer now. I want to look into nix or guix one of these days.

The general process would look something like:

1. Find all of the SSH keys you want to replace.
2. For each of thise keys, identify everywhere you use it to authenticate, and write this down! This list will form the basis of the rest of the plan. Make sure you list all of the accounts/servers you log in to, and don’t forget things like github or other external systems if you use them.

You’ll need to perform the following steps for each SSH key you are replacing:

1. Rename the public and private keys to something like old_id_rsa and old_id_rsa.pub (obviously use the same type name as your key, just prefix old_)
2. In your ~/.ssh/config, add a line telling SSH to use the old key as well as the new ones: IdentityFile ~/.ssh/old_id_rsa (change the key filename as aporopriate)
3. Check you can still log in to the servers you could log in to before. It should still be using the old key, just with a different filename, so it should still work.
4. Generate your new SSH keys ssh-keygen -t ed25519
5. Log in to each server and ADD the new ~/.ssh/id_ed25519.pub key to the authorized_keys file or equivalent mechanism. Do not remove the old public key yet.
6. Remove the IdentityFile line from your ~/.ssh/config
7. Check you can log in to all your systems. This will validate that your new key is working.
8. Remove your old public key from the authorized_keys file on each server you log in to.

Depending on your threat model you’re going to want to do this more or less often, and so you may want to consider automating it with sonething like ansible if it’ll be a regular job.

This generally referred to as Key Rotation. It applies to everything from SSH keys, to API keys in running apps.

There are automated ways to do this with ease, but it’s very simple to do with a single script, and some sort of secure key/value store (bitwarden, Vault, etcd…whatever).

The process is basically something like:

1. Create a script that runs on cron to check for a key at your k/v store at an expected location, like /ssh_keys/host1-private-12.1.25 and /ssh_keys/host1-public-12.1.25
2. Deploy this script to all machines you wish to regularly rotate keys on and ensure running properly
3. Generate new keys and put them in your k/v store at some versioned location/path like /ssh_keys/host1-private-12.21.25 and /ssh_keys/host1-pub-12.21.25
4. Update your local script that regularly grabs these updated keys to point to the new version uploaded, bonus if your store can symlinkto some other locations like /ssh_keys/host1-private-current
5. Wait X period of time to ensure all hosts get whatever key they need

Your script can clear the old keys if needed but simply validating them in the access change serves the same effect. Up to you.

I moved over to certificates a while ago.

smallstep.com/blog/use-ssh-certificates/

The best way is to use ssh-ca and certificate based auth.