If you aren’t deploying a container image without shell/secure-shell support (like distroless), then see if the cmd
flyctl ssh issue
patches it up for you.
Ref: fly ssh: Error establish key failed: key exists and override not set - #2 by kurt
If not, it seems like an internal Fly networking/dns issue and may need an escalation to their eng team, short of recreating / changing regions the app deploys to.