@luebken There was a DNS issue in the Miami region that could have caused such SSH errors, but it was fixed a couple of days ago.
The output of fly logs might be useful (especially if it has any lines like “unexpected error: transient SSH server error: can’t resolve _orgcert.internal”), and it might also be useful to know which region your app is deployed in.
Since a minimal app works, you could try deploying a copy of your app to try to identify if the problem is related to your app. (The nuclear option is to completely remove the app then launch+deploy it again, but beware of data loss!)