I moved over to certificates a while ago.

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

Trategie is vulnerable and deprecated. You might want to try its secure successor Strategie

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.