I'm trying to connect to Jenkins Slave machines with SSH username and Certificate. No password. The public certificate on Jenkins slave resides in public certificate in /home/jenkins/.ssh/authorized_keys/id_rsa.pub.

You can find the error below:
[07/17/13 12:40:16] [SSH] Opening SSH connection to MY_HOSTNAME:22.
ERROR: Server rejected the private key for jenkins (credentialId:b2bd2fe3-22e9-45dc-a7d1-xxxxxxxxxxxx/method:publickey)
[07/17/13 12:40:17] [SSH] Authentication failed.
hudson.AbortException: Authentication failed.
at hudson.plugins.sshslaves.SSHLauncher.openConnection(SSHLauncher.java:954)
at hudson.plugins.sshslaves.SSHLauncher.launch(SSHLauncher.java:488)
at hudson.slaves.SlaveComputer$1.call(SlaveComputer.java:222)
at java.util.concurrent.FutureTask$Sync.innerRun(Unknown Source)
at java.util.concurrent.FutureTask.run(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(Unknown Source)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
at java.lang.Thread.run(Unknown Source)
[07/17/13 12:40:17] [SSH] Connection closed.