The major distros ship (yes, all of them. Even Slackware) with a script which will automatically create host keys when you start sshd for the first time.

Therefore, I have no experience of doing...