Just rename them, the users can still login (if not forbidden via logon rights at the AD user object level). You won't need to rejoin the domain. But don't forget to update DNS if the IPs are static.