I used Michael Lucas' book SSH Mastery (Chapter 7) for guidance. It was a couple of years back now and I didn't bother to jot down any notes, which means I found it easy. So I guess I might have followed this sentence in his book:
"If your server runs a recent OpenSSHversion run ssh-keygen -A as root to automatically generate all supported but missing host keys."
I'm not sure but I think you can also generate them in Putty. But take note of Merlin's advice, and if you have problems getting it to work, check the format. I have a vague memory of having to go back and insert a return at the end of a line or something like that. By no means difficult