This post is meant to be more of a sign post than anything else...
For any fresh installation, a connection via SSH to a remote machine results in the request to store the public key. You have to respond with the letters 'yes' in order to allow the connection to proceed. However, subsequent connections will require that the you enters your password.
To eliminate subsequent password requests you have to generate a unique (as per that instance) key using ssh-keygen then copy the public key that results to the remote host. Note that despite the fact that the first few characters of the keys are not unique (you can compare them between keys) the rest are. A cursory glance will miss this.
To generate a key type:
$ ssh-keygen -t algorithm
Possible algorithms are RSA ('rsa') and DSS ('dsa'). Note that this does not require superuser privileges. This creates a private and public key. For obvious reasons the private key should never be shared as it is the one that encrypts all out-going messages while the public key should be shared to enable remote hosts decrypt messages.
To copy the public key type:
$ ssh-copy-id -i ~/.ssh/id_algorithm.pub user@host
You will be required you to enter your password one last time after which you will not require it anymore. However, remember that this grants access to anyone who connects from your local host hence this should be applied with caution. If your machine is stolen or compromised then all remote hosts are vulnerable.
Once the key is generated, it can be used on other remote hosts without regenerating the keys. If another ssh-keygen is run and the keys are overwritten, then all remote hosts previously configured will have to be configured again. Therefore, it is ill-advised to run ssh-keygen unless you want to change the keys afresh.