Booom! After reinstall of one of our servers I got into this. Weird error. It’s caused by paramiko. There’s no code fix available, but reason is simple – and fix too.

Connect to your box, and simply remove two files from /etc/ssh directory

root@limone:/# ls -la /etc/ssh/
total 168
drwxr-xr-x  2 root root   4096 Apr 24 15:31 .
drwxr-xr-x 82 root root   4096 Apr 24 16:00 ..
-rw-r--r--  1 root root 136156 Feb  8  2013 moduli
-rw-r--r--  1 root root   1669 Feb  8  2013 ssh_config
-rw-------  1 root root    668 Apr 23 12:05 ssh_host_dsa_key
-rw-r--r--  1 root root    601 Apr 23 12:05 ssh_host_dsa_key.pub
-rw-------  1 root root    227 Apr 23 12:05 ssh_host_ecdsa_key
-rw-r--r--  1 root root    173 Apr 23 12:05 ssh_host_ecdsa_key.pub
-rw-------  1 root root   1675 Apr 23 12:05 ssh_host_rsa_key
-rw-r--r--  1 root root    393 Apr 23 12:05 ssh_host_rsa_key.pub
-rw-r--r--  1 root root   2510 Apr 23 12:15 sshd_config

so, remove these two files:

-rw-------  1 root root  227 Apr 23 12:05 ssh_host_ecdsa_key
-rw-r--r--  1 root root  173 Apr 23 12:05 ssh_host_ecdsa_key.pub

Then clean up ~/.ssh/known_hosts  file on the box your’re running backup from

ssh-keygen -f "/root/.ssh/known_hosts" -R server_fqdn
ssh-keygen -f "/root/.ssh/known_hosts" -R server_ip

connect using ssh to backup server from that host (to write id_rsa keys into known_hosts file)

# ssh root@server_fqdn
Warning: the RSA host key for 'server_fqdn' differs from the key for the IP address 'server_ip'
Offending key for IP in /root/.ssh/known_hosts:3
Matching host key in /root/.ssh/known_hosts:11
Are you sure you want to continue connecting (yes/no)? yes
root@server_fqdn's password:

and run duplicate again.

voila! :)