Somehow I am not able to configure the linux so that I can login as root without password (with ssh-keygen).
I have a bunch of linux VMs (for a test setup). I want to be able to ssh into the linux VMs using root but am not able to. It works fine with normal users.

I am on a mac, and want to be able to ssh into my linux VMs as me@linux & root@linux without password.

I did ssh-keygen, ssh-copy-id root@linux, ssh-copy-id me@linux. Following this I can ssh me@linux fine, without needing the password, but 'ssh root@linux' still asks for password.

/etc/ssh/sshd_config file has following settings

PermitRootLogin yes
#StrictModes yes
#MaxAuthTries 6
#MaxSessions 10

RSAAuthentication yes
PubkeyAuthentication yes

I tried doing ssh -v to get more debugs and I see the following difference.

for ssh me@linux (successful login)

-------------------------
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /Users/me/.ssh/id_rsa
debug1: Server accepts key: pkalg ssh-rsa blen 279
debug1: read PEM private key done: type RSA
debug1: Authentication succeeded (publickey).
Authenticated to a.b.c.d ([a.b.c.d]:22).
debug1: channel 0: new [client-session]
debug1: Requesting no-more-sessions@openssh.com
debug1: Entering interactive session.
debug1: Sending environment.
debug1: Sending env LANG = en_US.UTF-8
Last login: Thu Oct 25 00:47:21 2012 from a.b.c.e

---------------------------
for root@linux (failed)

debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /Users/me/.ssh/id_rsa
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Trying private key: /Users/me/.ssh/id_dsa
debug1: Next authentication method: password
root@a.b.c.d's password:

Looks like I am missing a setting or two in sshd_config file? Any help is appreciated.

The reason is you are not root when you do this, but (assuming you've done the setup correctly), the relevant private-key is in root's home dir (actually /root/.ssh).
Look at this msg in your root attempt
To use public key cxns, you have to be logged in as the correct user.

Thanks for the response Chris, I tried that earlier as well but doesn't work

sh-3.2# ssh -v root@a.b.c.d
OpenSSH_5.9p1, OpenSSL 0.9.8r 8 Feb 2011
debug1: Reading configuration data /etc/ssh_config
debug1: /etc/ssh_config line 20: Applying options for *
debug1: /etc/ssh_config line 53: Applying options for *
debug1: Connecting to a.b.c.d [a.b.c.d] port 22.
debug1: Connection established.
debug1: permanently_set_uid: 0/0
debug1: identity file /var/root/.ssh/id_rsa type 1
debug1: identity file /var/root/.ssh/id_rsa-cert type -1
debug1: identity file /var/root/.ssh/id_dsa type -1
debug1: identity file /var/root/.ssh/id_dsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.9
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: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) 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: Server host key: RSA 94:e1:14:b9:36:9d:67:11:22:33:33:fa:fe:ba:8e:95
debug1: Host 'a.b.c.d' is known and matches the RSA host key.
debug1: Found key in /var/root/.ssh/known_hosts:1
debug1: ssh_rsa_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,gssapi-keyex,gssapi-with-mic,password
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /var/root/.ssh/id_rsa <------------
debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password
debug1: Trying private key: /var/root/.ssh/id_dsa
debug1: Next authentication method: password
root@a.b.c.d's password:

Usually, direct login to "root" is not permitted, simply because this particular ID is both universally-known and universally-lusted-after.

Far better to require the user to log in to user (say...) u35133, out of several hundred "dummy" accounts scattered among a potential namespace of 100,000 possible names, in order to be able to then successfully sudo specifically what must be done from that point forward.

Don't make it easier on the (self-proclaimed...) scr1pt k1dd13 l33t h4ckz0r than you must. Sometimes, even the slightest obstacle is more-than-enough to substantially reduce the "mosquito load" (i.e. pure-nuisances that can nevertheless suck your blood).

Be creative. More creative than this! A trivial-to-you, two-step process .. anything that you can dream up, really .. will be no more "inconvenient" to you than a one-step one that any fool could (and therefore will) immediately target.

There is also the setting:for sshd_config to limit the login for root to ssh-keys. You put the public key of yourself in root’s /root/.ssh/authorized_keys?

On the host where you are trying top log in root will need a .ssh/authorized_keys file. Confirm this contains a suitable public entry.
What do the server-side logs say?
see SSH FAQ www snailbook com /faq