This was the problem that I faced these days; and the answer to it is very simple
First thing you have to do is to install putty tools in linux :
$app-get install putty-tools
Then, just generate the new private key, using puttygen program
$puttygen putty-generated-key.ppk -O private-openssh -o openssh-key-name
You see, everything is very simple.
Also, if you want to generate the public key, you can use the following command:
puttygen ‐L putty-generated-key.ppk >> authorized-key-location/public-key.pub