Возможно ли заменить военный билет, не проходя еще раз службу?

Здравствуйте, Александр!

Из Вашего вопроса не понятно, по какому основанию Вы как гражданин России стояли на воинском учете в Приднестровье.

Если на тот момент Вы имели гражданство Молдавии, а впоследствии получили российское гражданство, то по законодательству РФ Вы должны встать на воинский учет в РФ и проходить службу.

В соответствии со ст.23 Федерального закон от 28.03.1998 N 53-ФЗ «О воинской обязанности и военной службе»

1. От призыва на военную службу освобождаются граждане:
а) признанные ограниченно годными к военной службе по состоянию здоровья;
б) проходящие или прошедшие военную службу в Российской Федерации;
в) проходящие или прошедшие альтернативную гражданскую службу;
г) прошедшие военную службу в другом государстве в случаях, предусмотренных международными договорами Российской Федерации;
д) — е) исключены. — Федеральный закон от 19.07.2001 N 102-ФЗ.
2. Право на освобождение от призыва на военную службу имеют граждане:
а) имеющие предусмотренную государственной системой научной аттестации ученую степень;
б) являющиеся сыновьями (родными братьями):
военнослужащих, проходивших военную службу по призыву, погибших (умерших) в связи с исполнением ими обязанностей военной службы, и граждан, проходивших военные сборы, погибших (умерших) в связи с исполнением ими обязанностей военной службы в период прохождения военных сборов;
граждан, умерших вследствие увечья (ранения, травмы, контузии) либо заболевания, полученных в связи с исполнением ими обязанностей военной службы в период прохождения военной службы по призыву, после увольнения с военной службы либо после отчисления с военных сборов или окончания военных сборов.
3. Не подлежат призыву на военную службу граждане:
а) отбывающие наказание в виде обязательных работ, исправительных работ, ограничения свободы, ареста или лишения свободы;
б) имеющие неснятую или непогашенную судимость за совершение преступления;
в) в отношении которых ведется дознание либо предварительное следствие или уголовное дело в отношении которых передано в суд.
4. Граждане, признанные не годными к военной службе по состоянию здоровья, освобождаются от исполнения воинской обязанности.

С Молдавией такого международного соглашения, насколько я знаю, нет.

Возможно у Вас есть другие основания для освобождения от службы.