My wife and I have identical phones, both configured by me, both with ProtonVPN, netshield on, kill switch enabled.
My notifications are instant. I don't have play store / services installed.
She has play store and play services installed. Her notifications are delayed. Her delay is probably due to battery optimization and/or play store permissions set only for notifications and sensors. Play services permissions are network, notifications and sensors, battery is optimized.