Ниже приведены текущие настройки в моей системе: python: 2.7.14 paramiko (2.0.0) bcrypt (3.1.3) криптография (2.0.3) pyasn1 (0.3.6) PyNaCl (1.1.2)
Paramiko 2.0.0 определенно не поддерживает ключи Ed25519.
Вам необходимо срочно обновить.