Восстановить военный билет можно только через военкомат по новому месту жительства - в Хакасии, и полгода ожидания ответа из Красноярска это уже явное затягивание, которое можно и нужно обжаловать, а не просто ждать.
По п. 50 Постановления Правительства РФ № 719 при утрате военного билета гражданин обязан обратиться в военкомат по месту жительства с заявлением, а комиссариат делает запрос по прежнему месту учета для подтверждения данных - это стандартная процедура, но конкретного срока её проведения закон не устанавливает жёстко, из-за чего военкоматы часто затягивают на месяцы. При этом на период проверки данных гражданину должно выдаваться временное удостоверение взамен военного билета - именно оно закрывает вопрос с работодателем, пока делают новый бланк. Если такое удостоверение вашему знакомому не выдали - это уже нарушение с их стороны.
Плюс имейте в виду: за утрату билета обычно выносят постановление по ст. 21.7 КоАП РФ (небрежное хранение) - штраф небольшой, но это отдельная процедура, которая иногда тоже тормозит выдачу нового билета, потому что в военкомате ждут, пока пройдёт административка.
Полгода это ненормально долго. Тут нужно действовать активно - письменно фиксировать бездействие и требовать временный документ, а если не подействует - идти выше.