Make sure that you have a minimum frequency range to search.
I am based in Brazil, and I set the QBAND like this:
AT+QBAND=1,28
Band 28 for NB-IoT here in Brazil, reduces considerably the search time.
In the past, I was using more bands, and that took a quite long time.
To make sure about your case, you must go through your country’s frequency regulation to see what frequencies are allowed and so on.
Tip: if you are flashing your module every time, I recommend checking my suggestion here: faster network registration after reflashing