Общая обязанность состоять на воинском учёте установлена ст. 8 того же закона. Исключения из неё — освобождённые от воинской обязанности, проходящие военную службу, женщины без военно-учётной специальности и постоянно проживающие за рубежом. Вы не относитесь ни к одной из этих категорий: вы — мужчина призывного возраста (до 45 лет), приобретший гражданство, не освобождённый от воинской обязанности и проживающий в России. Следовательно, вы обязаны состоять на воинском учёте. Неисполнение этой обязанности является нарушением законодательства, но само по себе не лишает вас паспорта как документа, удостоверяющего личность. Однако при замене паспорта (в 45 лет) возникает процедура проверки воинского учёта: Положение о паспорте гражданина РФ и административные регламенты МВД предусматривают представление документов воинского учёта для мужчин, не достигших 50 лет. Поскольку вы не состояли и не состоите на учёте, военный билет или приписное свидетельство у вас отсутствуют. Без них паспорт вам могут не заменить до урегулирования вопроса с военкоматом.
Статья 8. Организация воинского учета 1. Граждане обязаны состоять на воинском учете, за исключением граждан: освобожденных от исполнения воинской обязанности в соответствии с настоящим Федеральным законом; проходящих военную службу; женского пола, не имеющих военно-учетной специальности; постоянно проживающих за пределами Российской Федерации.
— Федеральный закон от 28.03.1998 № 53-ФЗ «О воинской обязанности и военной службе», ст. 8
Ст. 9 рассматриваемого закона уточняет порядок первоначальной постановки на учёт лиц, приобретших гражданство: она осуществляется военными комиссариатами в течение всего календарного года. Это означает, что военкомат должен был поставить вас на учёт самостоятельно либо вы должны были инициировать эту процедуру в любой момент после получения гражданства. Факт того, что вы не получали уведомлений и не вставали на учёт, не освобождает вас от обязанности его пройти — и до 45 лет, и после. На момент обращения за заменой паспорта это обстоятельство будет иметь критическое значение: без отметки о воинском учёте или без справки из военкомата уполномоченный орган (МВД) откажет в замене паспорта, сославшись на необходимость соблюдения требований воинского учёта.
Статья 9. Первоначальная постановка граждан на воинский учет... 2. Первоначальная постановка на воинский учет... лиц, приобретших гражданство Российской Федерации... осуществляется военными комиссариатами в течение всего календарного года.
— Федеральный закон от 28.03.1998 № 53-ФЗ «О воинской обязанности и военной службе», ст. 9
В представленном контексте НПА отсутствуют нормы, прямо регулирующие перечень документов для замены паспорта (это сфера Указа Президента РФ № 232 и Административного регламента МВД). Однако из системного анализа обязанности состоять на воинском учёте (ст. 8) и последствий её неисполнения следует, что замена паспорта без военного билета или документа, подтверждающего отношение к воинскому учёту, для мужчины вашего возраста (скоро 45 лет) невозможна — до тех пор, пока вы не исполните обязанность по первичной постановке на учёт в военкомате.