import paramiko
import binascii
ssh = paramiko.SSHClient()
ssh.set_missing_host_key_policy(paramiko.AutoAddPolicy())
ssh.connect(hostname='HOSTNAME', username='USERNAME', password='PASSWORD')

#... after connection is successful
keys = ssh.get_host_keys()
key = keys['HOSTNAME']['ssh-rsa']
print binascii.hexlify(key.get_fingerprint())
# key.get_fingerprint() returns the md5 hash of
# the public part of the key (whatever that means)

a42273f83e62d65cc87231a2ba33eff3

RSA 1b:c2:f4:8f:f2:86:fc:f2:96:ba:cc:24:41:e9:d7:86
DSA 36:b9:1f:ad:53:b5:c4:38:78:bf:cb:9d:38:fa:44:ce