1. Your public part of your SSH key pair *MUST* be ~/.ssh/authorized_keys on all destination hosts. That file *MUST* have a perms of 0600 (-rw-------) and be owned by the user.
2. ALL Destination hosts must *NOT* disallow Forwarded Authentication. (this being a key point here, stupid as it may be, it is a choice over zealous admins use sometimes) ("PubkeyAuthentication yes" is usually default and only works with version 2 anyway)
3. You have your local workstation's ssh-agent running and loaded with your private part of your SSH key pair.
4. You must either by config (~/.ssh/config or /etc/ssh/config) have "ForwardAgent yes" on all hosts or use "ssh -A" on every attempt to want to forward from there. If you do not use "ssh -A" (or have config) on the "next" host, you will only be allowed to forward from that last host and no successive host.
example of #4: I ssh into relay host without ForwardAgent yes or with without "-A" I can not login via key-authentication. If I ssh into relay host "ssh -A relayhost" my authentication will be forwarded one additional hop to the next host or "ssh nexthost" will auto present the key-auth. If I have "ForwardAgent yes" or use "ssh -A nexthost" I can then chain another "ssh thirdhost" and be authenticated via key-auth and so on and so on.
*ALL* of these following machines have my public part of my key pair which is snipped to make it screen width friendly, otherwise it'd be over 600 characters wide:
ssh-dss AAAAB3NzaC1kc3MAAACBAKLDN [SNIP] +atgu8agE= greg@gregfolkert.net
That entry is in *EVERY* ~/.ssh/authorized_keys with a "0600" permissions (-rw-------) on that file.
Here is a "cleansed" screen scrape output. to help make it clear and show what happens if you don't use the appropriate ForwardAgent flags of config. Most of these times are "Mountain Time".
greg@maxime:~ [0] $ ssh-add -l
1024 e2:58:eb:64:a0:37:71:09:4d:a1:1d:64:0e:9c:49:2c /home/greg/.ssh/id_dsa (DSA)
greg@maxime:~ [0] $ set | grep SSH_AUTH
SSH_AUTH_SOCK=/tmp/ssh-FCn0s4UDkB6l/agent.3125
greg@maxime:~ [0] $ ssh -A relayhost.managedby.me
Last login: Thu Feb 28 18:52:03 2013 from myhomeip.net
[greg@relayhost greg]$ set | grep SSH_AUTH
SSH_AUTH_SOCK=/tmp/ssh-qIhpM16436/agent.16436
[greg@relayhost greg]$ ssh secondhost
Last login: Thu Feb 28 18:53:05 2013 from relayhost
[greg@secondhost ~]$ set | grep SSH_AUTH
[greg@secondhost ~]$ ssh thirdhost
greg@thirdhost's password:
Last login: Mon Dec 10 09:35:32 2012 from relayhost
[greg@thirdhost ~]$ exit
Connection to thirdhost closed.
[greg@secondhost ~]$ exit
Connection to secondhost closed.
[greg@relayhost ~]$ ssh -A secondhost
Last login: Thu Feb 28 18:59:03 2013 from relayhost
[greg@secondhost ~]$ set | grep SSH_AUTH
SSH_AUTH_SOCK=/tmp/ssh-qpaPi28302/agent.28302
[greg@secondhost ~]$ ssh thirdhost
[greg@thirdhost ~]$ set | grep SSH_AUTH
[greg@thirdhost ~]$ ssh fourthhost
greg@fourthhost's password:
(Control C out of it)
[greg@thirdhost ~]$ exit
Connection to thirdhost closed.
[greg@secondhost ~]$ ssh -A thirdhost
Last login: Thu Feb 28 19:01:49 2013 from secondhost
[greg@thirdhost ~]$ set | grep SSH_AUTH
SSH_AUTH_SOCK=/tmp/ssh-xTngh18439/agent.18439
[greg@thirdhost ~]$ ssh fourthhost
Last login: Mon Dec 10 08:22:42 2012 from relayhost
[greg@fourthhost ~]$ set | grep SSH_AUTH
[greg@fourthhost ~]$ exit
Connection to fourthhost closed.
[greg@thirdhost ~]$ exit
Connection to thirdhost closed.
[greg@secondhost ~]$ exit
Connection to secondhost closed.
[greg@relayhost greg]$ exit
Connection to relayhost.managedby.me closed.
greg@maxime:~ [0] $