I wanted to post because I had been wrestling with an issue for a while this morning. We have a windows host that needs to connect to a Solaris 9 server running Sun_SSH. The client (Windows) generated an F-Secure public key which was copied into ~/.ssh/authorized_keys. However, the server would still always prompt for a password. After much reading on google, I came across the solution. You need to convert the public key from F-Secure format into SUN format. ssh-keygen can do it for you ( do this in the .ssh directory and substitute with actual filenames):
Hope this helps someone who has this issue in the future.