Based on your logs, it really looks like the wrong ssh key is being used.
I created an account, added an new ssh key I generated with ssh-keygen (no parameters)
Debug snippet shows the following;
debug1: Offering RSA public key: /root/.ssh/id_rsa
debug1: Server accepts key: pkalg ssh-rsa blen 279
debug1: read PEM private key done: type RSA
debug1: Authentication succeeded (publickey).
ssh-keygen -l showed a fingerprint which matched the fingerprint displayed in the cloudbees portal.
Its a bit of a stretch but... can you tell me what parameters you added to 'ssh-keygen' when generating the key? You may have stumbled on an unsupported key format..
Otherwise, start again with a new key..