Распарсь GSV. Посмотри, сколько видимых спутников и какие у них
уровни сигнала. Должно быть хотя бы несколько с уверенным сигналом.
Что такое уверенный сигнал конкретную цифирь сказать сложно,
зависит от всякого, в том числе от модели приёмника. В GGA есть
параметр - кол-во используемых для построения спутников, обрати
внимание на него. Первым делом, конечно, определяет время, для этого много не надо. Для построения навигационного решения требуется время и несколько спутников с уверенным приёмом. Питание без нужды лучше не отключать, чтобы не стартовать потом в холодную.
Описание NMEA: https://wiki.iarduino.ru/page/NMEA-0183