Sounds like an Apple server problem. Something on the i-Device, waiting for an (to be expected - given Apple problems) overly-busy Apple server.
I have had the same issue. It’s very annoying. 12 Pro, 14.3. I have turned my phone on and off a few times for other reasons and this problem still persists.
The server’s job should only be the sending of said message. I understood it happens prior to that phase.
Also, if it were server related, we wouldn’t see temporary improvements with client restarts.