I followed the simple guide in the forum
but was still unable to use my keys. Turns out my keys were DSA, and FreeSSHD only seems to know about RSA keys. I generated some RSA keys and everything was fine. The guide is somewhat misleading, what worked for me was creating a file in C:\Program Files\FreeSSHD\username and copying the contents of my RSA public key.
The error I was getting before was:
02-09-2009 09:11:09 IP 172.16.43.38 SSH charlie submitted a bad key.
I now get
02-09-2009 16:44:32 IP 172.16.43.38 SSH charlie successfully logged on using public key.