SSH key based authentication working intermittently

We have a dev server running jenkins with various jobs that run shell scripts that connect to our live server via SSH (using key-based authentication).

This doesn't seem to work reliably.

If I test the SSH connection on its own by logging in to the dev server as the "jenkins" user and then SSH'ing to the live server, the authentication works and logs me in without the password prompt.

If I run one of the jenkins jobs manually it works most of the time (although one failed this morning prompting me to write this ticket) but if I automate the job to run nightly it fails most of the time (I think it has worked once).

The point of failure each time is at the SSH connection:

> ssh -T nepton@xxx
> Permission denied, please try again.
> Permission denied, please try again.
> Permission denied (publickey,password).

Any help would be greatly appreciated as I'm completely stuck and Linux is definitely not my area of expertise.

Additional Information:

• I generated the public key on Dev (whilst logged in as "jenkins" user) using:
  ssh-keygen -t rsa
• I copied the key to the live server using: ssh-copy-id -i ~/.ssh/id_rsa.pub nepton@xxx

Permissions of /var/lib/jenkins/.ssh/ on Dev are:

drwx------  2 jenkins jenkins 4096 Apr  4 13:31 .
drwxr-xr-x 13 jenkins jenkins 4096 Apr  4 13:38 ..
-rw-------  1 jenkins jenkins 1679 Apr  4 13:31 id_rsa
-rw-r--r--  1 jenkins jenkins  400 Apr  4 13:31 id_rsa.pub
-rw-r--r--  1 jenkins jenkins 1338 Apr  4 13:33 known_hosts

Permissions of /home/nepton/.ssh/ on the Live server are:

drwx------ 2 nepton nepton 4096 Mar 20 17:37 .
drwx------ 4 nepton nepton 4096 Apr  2 10:52 ..
-rw------- 1 nepton nepton 2005 Apr  8 10:23 authorized_keys
-rw-r--r-- 1 nepton nepton 1106 Apr  1 10:39 known_hosts

• I'm running the latest LTS version of Ubuntu and the standard SSH package on both servers.

Debug information

ssh -v -T -i /var/lib/jenkins/.ssh/id_rsa nepton@xxx
OpenSSH_5.9p1 Debian-5ubuntu1, OpenSSL 1.0.1 14 Mar 2012
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to xxx [xx.xxx.xx.xxx] port 22.
debug1: Connection established.
debug1: identity file /var/lib/jenkins/.ssh/id_rsa type 1
debug1: Checking blacklist file /usr/share/ssh/blacklist.RSA-2048
debug1: Checking blacklist file /etc/ssh/blacklist.RSA-2048
debug1: identity file /var/lib/jenkins/.ssh/id_rsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.9p1 Debian-5ubuntu1
debug1: match: OpenSSH_5.9p1 Debian-5ubuntu1 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.9p1 Debian-5ubuntu1
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA xxx
debug1: Host 'xxx' is known and matches the ECDSA host key.
debug1: Found key in /var/lib/jenkins/.ssh/known_hosts:7
debug1: ssh_ecdsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /var/lib/jenkins/.ssh/id_rsa
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: password
debug1: read_passphrase: can't open /dev/tty: No such device or address
debug1: Authentications that can continue: publickey,password
Permission denied, please try again.
debug1: read_passphrase: can't open /dev/tty: No such device or address
debug1: Authentications that can continue: publickey,password
Permission denied, please try again.
debug1: read_passphrase: can't open /dev/tty: No such device or address
debug1: Authentications that can continue: publickey,password
debug1: No more authentication methods to try.
Permission denied (publickey,password).
Build step 'Execute shell' marked build as failure