I am trying to login with ssh keys and it is failing; output below. 
What I would like to do is to set up a nightly cron job for rsync and
have the server login with ssh with keys instead of using a
username/password


I have edited /etc/.ssh/ssh_config and set "RhostsAuthentication yes" on
both systems and done at /etc/init.d/ssh restart so that the new setting
would take effect.  

ssh -v -1 hostname
OpenSSH_3.6.1p2 Debian 1:3.6.1p2-11, SSH protocols 1.5/2.0, OpenSSL 0x0090702f
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Rhosts Authentication disabled, originating port will not be trusted.
debug1: Connecting to hostname [ip.address] port 22.
debug1: Connection established.
debug1: identity file /root/.ssh/identity type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_3.6.1p2 Debian 1:3.6.1p2-11
debug1: match: OpenSSH_3.6.1p2 Debian 1:3.6.1p2-11 pat OpenSSH*
Protocol major versions differ: 1 vs. 2
debug1: Calling cleanup 0x80623b0(0x0)


version 2 output below

ssh -v -2 hostname
OpenSSH_3.6.1p2 Debian 1:3.6.1p2-11, SSH protocols 1.5/2.0, OpenSSL 0x0090702f
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Rhosts Authentication disabled, originating port will not be trusted.
debug1: Connecting to hostname [ip.address] port 22.
debug1: Connection established.
debug1: identity file /root/.ssh/id_rsa type -1
debug1: identity file /root/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_3.6.1p2 Debian 1:3.6.1p2-11
debug1: match: OpenSSH_3.6.1p2 Debian 1:3.6.1p2-11 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_3.6.1p2 Debian 1:3.6.1p2-11
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-cbc hmac-md5 none
debug1: kex: client->server aes128-cbc hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'hostname' is known and matches the RSA host key.
debug1: Found key in /root/.ssh/known_hosts:4
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: publickey
debug1: Trying private key: /root/.ssh/id_rsa
debug1: Trying private key: /root/.ssh/id_dsa
debug1: Next authentication method: keyboard-interactive
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: password
root@hostnames password: