Since you're using a FIPS yubikey, you need to use FIPS algorithms. Try generating an ssh key using rsa or ecdsa instead.
Solution source? I run fips openshift clusters, and our authentication to github using deploykeys fails unless we use fips compatible ciphers (rsa/ecdsa).