I originally had a slightly different starting point, as I'm on Lineage-OS (23.2) + Magisk and not on GrapheneOS. But nevertheless, I want to share how I was able to resolve this, so it might help others:
- I changed from LineageOS builds to microG's own LineageOS builds, as the app was working fine on a friends phone with those builds,
- Unfortunately, I still had to reset the app (wipe data/re-install). However, I then could simply re-authenticate myself using my phone's NFC + my personalausweis/ec-card (select new device + order registration data during setup of the TAN app).
I know, that this won't help for most of you, as you're running GrapheneOS. But when I googled the issue I'm having on LineageOS with the S-PushTAN App, I stumbled accross this post and hope to help others who do so too.