Op 1 oktober 2016 leidde Xhaja zijn eerste wedstrijd in de Albanese nationale competitie. Tijdens het duel tussen Skënderbeu Korçë en Vllaznia Shkodër (3–0) trok de leidsman viermaal de gele kaart.[1] In Europees verband debuteerde hij op 5 juli 2018 tijdens een wedstrijd tussen Gzira United en Sant Julià in de voorronde van de UEFA Europa League; het eindigde in 2–1 en de Albanese leidsman gaf zes gele kaarten, waarvan twee aan dezelfde speler.[2] Zijn eerste interland floot hij op 10 oktober 2019, toen Kosovo met 1–0 won van Gibraltar. Tijdens dit duel gaf Xhaja één gele kaart.[3]