unknown key type ed25519 on OSX Yosemite

[takosuke]

OS / Environment

OS X Yosemite 10.10.5

Ansible version

2.2.0.0

Version of components from requirements.txt

adal==0.4.5
ansible==2.2.0.0
apache-libcloud==1.5.0
appdirs==1.4.3
asn1crypto==0.22.0
azure==2.0.0rc5
azure-batch==0.30.0rc5
azure-common==1.1.4
azure-graphrbac==0.30.0rc5
azure-mgmt==0.30.0rc5
azure-mgmt-authorization==0.30.0rc5
azure-mgmt-batch==0.30.0rc5
azure-mgmt-cdn==0.30.0rc5
azure-mgmt-cognitiveservices==0.30.0rc5
azure-mgmt-commerce==0.30.0rc5
azure-mgmt-compute==0.30.0rc5
azure-mgmt-keyvault==0.30.0rc5
azure-mgmt-logic==0.30.0rc5
azure-mgmt-network==0.30.0rc5
azure-mgmt-notificationhubs==0.30.0rc5
azure-mgmt-nspkg==1.0.0
azure-mgmt-powerbiembedded==0.30.0rc5
azure-mgmt-redis==0.30.0rc5
azure-mgmt-resource==0.30.0rc5
azure-mgmt-scheduler==0.30.0rc5
azure-mgmt-storage==0.30.0rc5
azure-mgmt-web==0.30.0rc5
azure-nspkg==1.0.0
azure-servicebus==0.20.2
azure-servicemanagement-legacy==0.20.3
azure-storage==0.32.0
boto==2.46.1
boto3==1.4.4
botocore==1.5.38
certifi==2017.1.23
cffi==1.10.0
chardet==2.3.0
cryptography==1.8.1
docutils==0.13.1
dopy==0.3.5
enum34==1.1.6
futures==3.0.5
idna==2.5
ipaddress==1.0.18
isodate==0.5.4
Jinja2==2.8
jmespath==0.9.2
keyring==10.3.1
MarkupSafe==1.0
msrest==0.4.1
msrestazure==0.4.7
oauthlib==2.0.2
packaging==16.8
paramiko==2.1.2
pyasn1==0.2.3
pycparser==2.17
pycrypto==2.6.1
PyJWT==1.4.2
pyOpenSSL==16.2.0
pyparsing==2.2.0
python-dateutil==2.6.0
PyYAML==3.12
requests==2.13.0
requests-oauthlib==0.8.0
s3transfer==0.1.10
six==1.10.0

Summary of the problem

Generate the SSH private key fails with error unknown key type ed25519

possibly outdated open-ssh?

Steps to reproduce the behavior

./algo choosing digitalocean as provider and No to every question

Full log

  What provider would you like to use?
    1. DigitalOcean
    2. Amazon EC2
    3. Microsoft Azure
    4. Google Compute Engine (only for testing, see issue #369)
    5. Install to existing Ubuntu 16.04 server

Enter the number of your desired provider
: 1

Enter your API token. The token must have read and write permissions (https://cloud.digitalocean.com/settings/api/tokens):
[pasted values will not be displayed]
:

Name the vpn server:
[algo.local]:

  What region should the server be located in?
    1.  Amsterdam        (Datacenter 2)
    2.  Amsterdam        (Datacenter 3)
    3.  Frankfurt
    4.  London
    5.  New York         (Datacenter 1)
    6.  New York         (Datacenter 2)
    7.  New York         (Datacenter 3)
    8.  San Francisco    (Datacenter 1)
    9.  San Francisco    (Datacenter 2)
    10. Singapore
    11. Toronto
    12. Bangalore
Enter the number of your desired region:
[7]: 2

Do you want macOS/iOS clients to enable "VPN On Demand" when connected to cellular networks?
[y/N]: n

Do you want macOS/iOS clients to enable "VPN On Demand" when connected to Wi-Fi?
[y/N]: n

Do you want to install a DNS resolver on this VPN server, to block ads while surfing?
[y/N]: n

Do you want each user to have their own account for SSH tunneling?
[y/N]: n

Do you want to apply operating system security enhancements on the server? (warning: replaces your sshd_config)
[y/N]: n

Do you want the VPN to support Windows 10 clients? (requires RSA certificates and key exchange, less secure)
[y/N]: n

Do you want to retain the CA key? (required to add users in the future, but less secure)
[y/N]: n

PLAY [Configure the server] ****************************************************

TASK [setup] *******************************************************************
ok: [localhost]

TASK [Generate the SSH private key] ********************************************
fatal: [localhost -> localhost]: FAILED! => {"changed": true, "cmd": "echo -e 'n' | ssh-keygen -C algo@ssh -t ed25519 -f configs/algo.pem -q -N \"\"", "delta": "0:00:00.025021", "end": "2017-04-10 12:05:45.252851", "failed": true, "rc": 1, "start": "2017-04-10 12:05:45.227830", "stderr": "unknown key type ed25519", "stdout": "", "stdout_lines": [], "warnings": []}

PLAY RECAP *********************************************************************
localhost                  : ok=1    changed=0    unreachable=0    failed=1

[takosuke]

Solved by updating openssh in Yosemite via homebrew to current version 7.5. Hoping it doesn't break anything, as all guides for doing this in Yosemite are outdated