For the last step you would need clusterssh (cssh command).
Create a text file called SERVERS where there is one server per line (e.g.
user@someserver.com). Assuming you already have public key access to all of these servers and can login without being prompted for a password you could do something like the following.
Code:
cat SERVERS | while read server;do scp .ssh/new_key.pub ${server}: ;done
cssh $(cat SERVERS | tr '\n' ' ')
When you're using cssh on all of the servers at once run the following command sequence.
Code:
cat new_key.pub >> .ssh/authorized_keys
You should now be able to log into all of the servers using the new key.
Code:
ssh -i .ssh/new_key user@someserver.com
Then you can use cssh to delete the old public key out of ~/.ssh/authorized_keys on all of the servers using a text editor like vim/emacs/nano. It should get the job done quick and dirty.