Oh finally I figured out how to use SSH pubkeys! It's simple:
1. Generate a public key on client
2. Somehow transfer it to server
3. Put it into user's authorized_ keys files
4. Now you can login as the user whp has your key in authorized_keys

Umm.. Change it to:
1. Generate a pair of ssh [rsa] keys [so you'd have both private and public key]
2. Transfer public key to another host's ~/.ssh/authorized_keys
3. Make sure ~/.ssh directory [or any other you are keeping keys and authorized_keys in] permissions are 600.

... Do the rest...