There could be (unfortunately) a couple of reasons so that we have to try to pinpoint the actual problem.
There is a help article on the Signal page what to try when such delays happen.
The article mentions the Google Play Services, which you (obviously) do not have, but the FOSS (free & open source) replacement microG. My Signal installation works flawlessly with it, so there is hope that your problem can be fixed.
Before you try the suggestions in the article, could you check whether Signal is registered in microG?
- Open the system settings
- Go to “System” > “MicroG” (you may have to expand the menu to see the “MicroG” option.)
- Select “Self check”. Do all entries have a checkmark?
- Go back to the MicroG main settings menu. Select “Cloud Messaging”.
- Is Signal listed here? If yes, what information do you see if you tap on the Signal entry? It should be stated that Signal is registered and the last time you received a push notification.
Maybe there are connection problems of microG to the Google infrastructure. Do you have other messaging apps? Do they work as expected? (Yes, microG has to connect to Google for push messaging, but it is done “as anonymously as possible” - this is however a topic for another time.)
EDIT: /e/OS uses an older microG version. The newest version should contain a fix to make the push connections more reliable. Hence, your problems may even be fixed with the next /e/OS update, which is on its way. (See for instance this GitHub issue.)