How to upgrade ssh on OS X 10.9 Mavericks without OS upgrade?

Running $ sudo brew install openssh with success, renaming the built-in /usr/bin/ssh* executables and running $ ssh-keygen -t ed25519 is not enough to use your ed25519 key with the new ssh version.

Disable Mac OS X ssh-agent

Your ssh logins will still only use the rsa key because the new ed25519 key is not known (to ssh-agent). ssh-add ~/.ssh/id_ed25519 will return:

Could not add identity xxx: agent refused operation

because Mavericks will run the old ssh-agent version or not at all. Better disable launching the built-in ssh-agent using: $ launchctl unload -w /System/Library/LaunchAgents/org.openbsd.ssh-agent.plist. Check with ps -ef that no ssh-agent is running, otherwise kill that pid.

Start new version ssh-agent automatically

Now it's time to learn your OS X terminal shell to start the newer ssh-agent automatically, once. When using zsh as shell, run $ nano .zshrc and append this:

# Automatically start ssh-agent once
if [[ "x" == "x`ps -x -u ${USER} | egrep '[s]sh-agent'`" ]] ; then
    ssh-agent | sed -e "/^echo/d" > ${HOME}/.ssh/agent-env
    source ${HOME}/.ssh/agent-env
    ssh-add -qk
else
    source ${HOME}/.ssh/agent-env
fi

Based upon code from: Automatically Start ssh-agent on Mac OS X

Now your newly opened terminal sessions will use the old rsa and new ed25519 keys.

Verify ssh-agent keys

The fingerprints of keys that are loaded in ssh-agent can be listed with $ ssh-add -l. Displayed order is important here. The keys are tried in the order as listed from top to bottom. This is also the order in which keys were imported. Current openssh source code has this key import priority for key-add:

1. RSA
2. DSA
3. ECDSA
4. ED25519
5. XMSS

Prefer ED25519 over RSA

In case you wish to prefer Ed25519 cryptography over RSA when both are available, you need to override the order in which the keys are loaded.

Thus change the ssh-add -qk in the code above to something like:

ssh-add -qk ~/.ssh/id_ed25519
ssh-add -qk ~/.ssh/id_rsa