When your phone loses a cellular network connection it tries to reconnect every few seconds for about a minute. It then gradually increases the time between checks with no response, eventually reaching 5 minutes or more. It does this because checking for a network uses a huge amount of energy, and doing it constantly would quickly delete the battery, as well as cause the phone to heat up. If you stay within range of a network for those 5 minutes it will reconnect on its own.
You can force it to do a new search by turning on Airplane mode for 15 - 30 seconds. Yo don’t have to turn the phone off and on again.
One other thing you can do is make sure Settings/Privacy/Location Services/System Services-Cell Network Search is on, and that Wi-Fi is also on (it doesn’t need to be connected, just on).