Kharja is een middenvelder en staat bekend om zijn fysieke gesteldheid en inzicht. Zijn wedstrijden bij Ternana (dat destijds in de Serie B actief was en nu in de Serie C1) zorgden ervoor dat hij een transfer naar AS Roma afdwong. Sinds het seizoen 2005/06 speelde Kharja voor het Italiaanse AS Roma. Van 2007 tot en met 2009 kwam hij uit voor AC Siena in de Serie A. Met zijn bepalende spel dwong hij een transfer af naar Genoa CFC. Eind januari 2011 neemt Inter Milan Kharja over van Genoa. Kharja tekende begin seizoen 2011-2012 een contract bij de Italiaanse subtopper ACF Fiorentina voor drie seizoenen.