This can happen when you protect your private keys with a default policy of DENY. The init script provided in the openssh-server rpm checks to see if the private key files exist under /etc/ssh. If the script can't find them, it executes ssh-kegen to generate them. The keys are actually there, ssh-keygen fails and the startup script exits.
To fix this, remove the check for the key files in the startup script:
start) # Create keys if necessary #do_rsa_keygen; <------------ Comment out these lines #do_dsa_keygen; echo -n "Starting sshd: " if [ ! -f $PID_FILE ] ; then sshd RETVAL=$? if [ "$RETVAL" = "0" ] ; then success "sshd startup" touch /var/lock/subsys/sshd else failure "sshd startup" fi fi echo ;; |