Adding your private key fingerprint to ~/.ssh/authorized_keys is usually one of the first things you do with new Linux boxen. ssh-copy-id is meant to make that task easy by internally using ssh to automatically add the fingerprint for your default or a specified private key to the remote host.
However, and something that took me a long time to realize is that, ssh-copy-id will try to authenticate to the remote host using private key authentication first since it just shells out to ssh. Where the problem comes in is when you have more than one or two private keys (I have 5): ssh will attempt to authenticate using each of your private keys in turn, and if the target ssh server is configured sanely it will disconnect you with a "too many authentication failures" message after 3 attempts and ssh-copy-id gives up.
To get around this you can use -o PubKeyAuthentication=no option to tell the ssh in ssh-copy-id to skip using PKI keys for authentication: ssh-copy-id -i ~/.ssh/id_ed25519 -o PubKeyAuthentication=no josh@host.domain