Like changing password at times, it is good practice to change your SSH key at times. But updating all servers with your new SSH key can be time consuming. Here is what i done to change my SSH key.
First i renamed my .ssh folder to .ssh-old
mv ~/.ssh ~/.ssh-old
Now generate new SSH keys with command
ssh-keygen -t rsa -b 4096 -C "firstname.lastname@example.org"
Lets remove SSH key cache with command
Add new and old SSH keys back in
ssh-add ~/.ssh/id_rsa ssh-add ~/.ssh-old/id_rsa
Verify both keys are listed with command
Now you will be able to use old and new key to login to servers. You can use new SSH key now on wards, replace old key with new key slowly, there is no rush as both of your keys will work.