Identical host keys!

I have compiled OpenSSH (and all its dependanies) from source.  They are stored in AFS and are shared by several machines.  We created a tarball of the contents of the /etc/ssh directory and distribute that to each target machine.  (tarball contains login_banner, moduli, ssh_config, ssh_known_hosts, ssh_prng_cmds,sshd_config).  We setup sshd so that it starts on boot (in rc3.d) and generate new keys for each machine. 

 

Then, we use ssh-keyscan to grab the public host keys for each machine (to put them into a central repository).  However I noticed that all of the hostkeys returned by ssh-keyscan are identical.  However, if you hop onto each box and look at the /etc/ssh/ssh_host_key files they are all different. 

 

What could be the source of my problem here?  I know that it can't be secure to have 3-4 dozen boxes with identical host keys.  What can I do to fix this?

 

Thanks for your help,

 

Felix Cat