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.