FWIW, this is not normal or expected, most users get their notifications more or less instantaneously. Maybe knowing this might help you search for information about whatever it may be that prevents this from working for you.
In that case, is Google Play Services allowed to run in the background / unrestricted / whatever? It is the means to delivering notifications for most apps.