First, check sshd is running on your server
service sshd status
This will say whether its running or not. If not running check whether its installed and the service is made to run on boot.
Once you do that, you need to generate a set of public and private keys.
Download puttygen from http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html
Following steps will explain public/private key generation using puttygen and setting the key at the server.
1. Run PuttyGen.exe and click on the generate button. Make sure the selection is on SSH-2 RSA
2. You need to create some randomness by moving your mouse pointer in an uneven way till the progressbar gets completed.
3. Set a passphrase (optional) but would be better. Confirm passphrase in next field
4. Set a comment ( a useful one to recognize your key)
5. Save private key as .ppk for putty. You can have a public key by clicking save public key as well. Save this as .pub (public)
6. Copy the key for authorized keys file (as seen below)
Go to your server. Under the user’s home directory, create a .ssh folder (if it isn’t there). under it, open a file authorized_keys2 and paste the key what you copied above (step 6).
Test your login to the linux server using PuTTY. This time it should ask you for your passphrase.
You can turn off the keyboard-interactive authorization method in the file /etc/ssh/ssh_config. Its a good idea to do this, as your passphrase is generally a longer more complicated password. And the fact that your password gets echoed to the log.
This tutorial is another version of http://www.grahamlange.com/setting_up_ssh.html . Read it in case you need more explanations.
Thanks !