We had a problem a couple of years ago with users having 10k unread notifications which would make notifications queries slow, and in turn make the PostAlert job slow.
We added a protection so it doesn’t happen anymore so much, but it may present a different performance characteristics on your setup.
Do you have users set to watch categories who are oblivious to notifications count?
Can you check the max number of unread notifications per user in your database?