First I start the ssh-agent with
eval `ssh-agent -s`
I confirm that SSH_AUTH_SOCK is set by running echo $SSH_AUTH_SOCK, which encouragingly returns /tmp/ssh-oCsFfHvR3345/agent.3345.
Yet when I run sudo ssh-add ~/.ssh/id_rsa, I get 
Could not open a connection to your authentication agent.
Moreover, ssd-add -l returns The agent has no identities.
                        
If you're running SSH commands through
sudothe environment variables won't be set.From
man sudoers:You can check which environment variables are available to your sudo commands by running
sudo env.The above would explain the behaviour you describe but you really should be running
sshcommands as a regular (non-super) user.