I have recently upgraded all the machines in my dept from P4's running Fedora4-9 to Core2's running Centos 5.3.
I am using the same sshd_config as before for my network. Using NIS to login, we used to be able to ssh from machine to machine without having to enter a password. I believe the line in the config for this was:
# For this to work you will also need host keys in /etc/ssh/ssh_known_hosts
RhostsRSAAuthentication yes

I have updated all the dsa,rsa keys in the /etc/ssh/ssh_known_hosts file and still cannot get passwordless logins to work. I know there are ways of doing this via the ~/.ssh/authorized_keys file, but this would be too cumbersome for such a large amount of users.

Any ideas what I may have done wrong? Here is my sshd_config:

# $OpenBSD: sshd_config,v 1.72 2005/07/25 11:59:40 markus Exp $

# This is the sshd server system-wide configuration file. See
# sshd_config(5) for more information.

# This sshd was compiled with PATH=/usr/local/bin:/bin:/usr/bin

# The strategy used for options in the default sshd_config shipped with
# OpenSSH is to specify options with their default value where
# possible, but leave them commented. Uncommented options change a
# default value.

Port 22
Protocol 2
#ListenAddress 0.0.0.0
#ListenAddress ::

# HostKey for protocol version 1
HostKey /etc/ssh/ssh_host_key

# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key

# Lifetime and size of ephemeral version 1 server key
KeyRegenerationInterval 3600
ServerKeyBits 768

# Logging
# obsoletes QuietMode and FascistLogging
#SyslogFacility AUTH
SyslogFacility AUTHPRIV
LogLevel INFO

# Authentication:
LoginGraceTime 120
PermitRootLogin yes
StrictModes yes

RSAAuthentication no
PubkeyAuthentication yes
AuthorizedKeysFile .ssh/authorized_keys

# Don't read the user's ~/.rhosts and ~/.shosts files
IgnoreRhosts no

# For this to work you will also need host keys in /etc/ssh/ssh_known_hosts
RhostsRSAAuthentication yes

# similar for protocol version 2
HostbasedAuthentication yes

# Change to yes if you don't trust ~/.ssh/known_hosts for
# RhostsRSAAuthentication and HostbasedAuthentication
IgnoreUserKnownHosts no

# To disable tunneled clear text passwords, change to no here!
PasswordAuthentication yes
PermitEmptyPasswords no

# Change to no to disable s/key passwords
ChallengeResponseAuthentication no

# Kerberos options
#KerberosAuthentication no
#KerberosOrLocalPasswd yes
#KerberosTicketCleanup yes
#AFSTokenPassing no
# Kerberos TGT Passing only works with the AFS kaserver
#KerberosTgtPassing no

# Set this to 'yes' to enable PAM keyboard-interactive authentication
# Warning: enabling this may bypass the setting of 'PasswordAuthentication'
#PAMAuthenticationViaKbdInt no

#X11Forwarding no
X11Forwarding yes
#X11DisplayOffset 10
#X11UseLocalhost yes
PrintMotd yes
PrintLastLog yes
KeepAlive yes
#UseLogin no
UsePrivilegeSeparation yes
PermitUserEnvironment yes
Compression yes

#MaxStartups 10
# no default banner path
#Banner /etc/ssh/banner
#VerifyReverseMapping no

# override default of no subsystems
Subsystem sftp /usr/libexec/openssh/sftp-server

# Allow and Deny settings
DenyUsers deniedusers
DenyGroups deniedssh
UseDNS no

What messages are you getting when you try to ssh from server to server?

One thing I find helpful when troubleshooting ssh is the following

In a window on the target server

sshd -D -d -d -d -p 999 ## this will start an ssh process listening on port 999 (or any port no in use), but will not put it into daemon mode

on the client server

ssh -v -p 999 <target server>

This will give you debug info stating what types of authentication it's trying and what's failing etc.