First time it's run, the sshd startup script (/etc/rc.d/init.d/sshd) notices that there is no /etc/ssh/ssh_host_rsa_key so it prints this message before creating one.
After creating the key, the startup script then starts the sshd daemon as normal.
I can see two possibilities: ssh-keygen is hanging for some reason; or the keygen succeeds, but the sshd startup hangs. Neither seems very likely on the face of it!
Cosmic: are you sure
it's the keygen part that hangs? There's definitely no green "OK" message for this stage?
There are a couple of ways to turn off key generation, if you can boot in single user mode, or rescue mode from the CD. First, you can disable key autocreation like this.
echo "AUTOCREATE_SERVER_KEYS=NO" >> /etc/sysconfig/sshd
Alternatively, you can pretend there already is a key.