Как правильней обрабатывать PHP скрипт с временем выполнения в 5-10 минут?
запускать подобные задачи в консольном режиме: в cli нет ограничения по времени.
Если выполнение процесса может оборваться в любой момент и вам нужно гарантировать его то я бы воспользовался очередями. Запаковываете часть вашего скрипта в консольную команду которую поставите на cron (ту часть которая отвечает за выборку пользователей для процессинга). Вторую часть, отвечающую за скачку файла по api и обновление юзера заворачиваете в консюмер на очереди. Таким образом сможете гарантировать что все ваши пользователи будут обработаны, а для тех что не завершились без ошибок (они вернутся в очередь) сможете добавить фикс для корректной их обработки. 
Все ваши воркеры (консюмеры) ставите на supervisord. Чтобы один консюмер не надрывался над вашей кучей - указываете кол-во процессов в конфиге супервизора.
Для решения задачи со временем можно сделать 2мя способами:
1. Во время выборки на консольной команде засылать в очередь только тех пользователей кто должен сейчас обновиться
2. Для каждого сообщения проставляете поле время. На конюсмере проверяете это время, если рано то кидаете обратно в очередь