Could not find 'ed25519' error when running Capistrano deploy

Error when run:

NotImplementedError: OpenSSH keys only supported if ED25519 is available
net-ssh requires the following gems for ed25519 support:
 * ed25519 (>= 1.2, < 2.0)
 * bcrypt_pbkdf (>= 1.0, < 2.0)
See https://github.com/net-ssh/net-ssh/issues/565 for more information
Gem::MissingSpecError : "Could not find 'ed25519' (~> 1.2) among 607 total gem(s)

To proceed, run the following and retry:

ssh-add