[knc1]

The "finger print" is only for human reference.
Putty uses a different algorithm than the industry standard programs do.

Same, same for any BSD (OpenSSH) compatible.
OpenSSH, Dropbear, etc.
Puttygen uses its own format for the keys, but they can be converted (imported) by OpenSSH keygen utility.

When you say you generate a "new key pair" do you mean you are generating a new Host key ?
ssh_host_rsa_key is used on the server side to hold the server's PRIVATE key.

Either Dropbear or OpenSSH on the server (I.E: KINDLE ) side will generate that, or re-generate that if you tell it too.

PuttyGen generates CLIENT key pairs.
You get to pick the <name>
You keep the <name> private key
You put the <name>.pub public key in the proper .ssh/authorized_keys file of the machine you wish to access (the Kindle). One key per line.