święceń tych, z dyspensą związaną z brakiem wymaganego wieku, udzielił mu w Kolbuszowej biskup Obłąk 28 czerwca 1964. Pierwszą placówką ks. Rzeszutka została parafia św. Józefa w Olsztynie, gdzie neoprezbiter był wikariuszem do 1965.
W 1965 wystąpił do biskupa olsztyńskiego Tomasza Wilczyńskiego o zgodę na podjęcie studiów z filologii klasycznej na Katolickim Uniwersytecie Lubelskim. Zgodę zwierzchnika diecezji otrzymał, ale z braku miejsc nie dostał się na studia w Lublinie i ostatecznie podjął je na Wydziale Humanistycznym Uniwersytecie Mikołaja Kopernika w Toruniu, będąc jednym z nielicznych księży studiujących na państwowej uczelni świeckiej w tym okresie. W czerwcu 1970 ukończył studia, a pracę Stosunek do śmierci i myśli z nią związane na przykładzie VII Księgi "Antologii Palatyńskiej" obronił w październiku 1971 z oceną bardzo dobrą, uzyskując magisterium filologii klasycznej. Już w 1970 z nominacji biskupa Drzazgi został wykładowcą łaciny i greki w seminarium w Olsztynie.