1 machine at the time
. Plus You only need one private and one public key.
Just like I wrote in my howto. https://andrzejlpclinuxos.wordpress.com/2011/01/29/passwordless-ssh-authentication-using-authentication-keys/
Public key that You generated goes to all the remote machines just like described in the howto.
Generate 1 private key 1 public key. Copy the public key to the remote machine that is running the ssh server. Set the permissions and disconnect. Try connecting again... Then copy the same public key to another remote machine. Set the permissions and reconnect. Should work 100%.
I thought my howto was really simple to follow...