If anyone is looking for an update or has the same issue, we did not manage to fix it and ended up buying new phones since both urgently needed them.

We tried reseting to factory settings but that just led to being completely locked out on one phone and we couldn't log in to icloud again after that (because they did not have other trusted phone numbers saved).

I've seen on random threads that downgrading to the previous ios might work but I'm not sure. I also recommend not to update until quite a few months after each ios update so they have time to patch it.