На этом всё, а сегодня на работе потребовалась справка об отсутствии гражданства КЗ так как до 2009 года была

Зайнар, добрый вечер.

Если у Вас уже на руках есть паспорт гражданина РФ, то по какой причине Ваш работодатель требует у Вас эту справку? Это не обосновано. 

Вы не обязаны предоставлять такую справку на работу. 

А так, если очень нужно не нужно звонить в УФМС, напишите заявление с просьбой дать Вам обратную связь относительно того, где сейчас Ваш паспорт. Подробно расписав всю предысторию.

  Здравствуйте.

Согласно  норме   Трудового кодекса РФ,  при приёме  на  работу   предоставляются  следующие  документы ( привожу неполный  отрывок  из  статьи) :

Статья 65. Документы, предъявляемые при заключении трудового договора
Если иное не установлено настоящим Кодексом, другими федеральными законами, при заключении трудового договора лицо, поступающее на работу, предъявляет работодателю:

паспорт или иной документ, удостоверяющий личность;

трудовую книжку и (или) сведения о трудовой деятельности (статья 66.1 настоящего Кодекса), за исключением случаев, если трудовой договор заключается впервые;
документ, подтверждающий регистрацию в системе индивидуального (персонифицированного) учета, в том числе в форме электронного документа;
документы воинского учета — для военнообязанных и лиц, подлежащих призыву на военную службу;
документ об образовании и (или) о квалификации или наличии специальных знаний — при поступлении на работу, требующую специальных знаний или специальной подготовки;

и  ещё  некоторые  документы, но в этом  списке  отсутствует  такой  документ как 

справка об отсутствии гражданства КЗ

но,  в  то  же  время,  Трудовым  кодексом РФ  установлено условие  о  том, что в отдельных случаях с учетом специфики работы, Трудовым кодексом РФ, иными федеральными законами, указами Президента Российской Федерации и постановлениями Правительства Российской Федерации может предусматриваться необходимость предъявления при заключении трудового договора дополнительных документов.

Зайнар, если  Вам нужна  подробная  консультация  по  защите Ваших  трудовых прав, тогда  заказывайте  консультацию  в  моём  чате — кнопка «общаться  в чате»