Two factor authentication for Terminal Services

Employees at my company have the unfortunate habit of sharing passwords and some have left the company. I don’t want to force everyone to change their passwords everytime an employee leaves, but our data could be put in jeopardy each time someone leaves. I’d love to introduce a two-factor solution for our terminal services implementation but don’t want to manage any special tokens. Does anyone have any ideas about how I could come up with a two-factor solution without a lot of new infrastructure?