Applying constraints to a large table

I Have had to rebuild a database for a customer and whilst most of this process has worked well I have come up against a problem.  On three tables when I run code similar to that below:

IF NOT EXISTS (SELECT * FROM sys.foreign_keys WHERE object_id = OBJECT_ID(N'[FK_GroupUserMap_User]') AND parent_object_id = OBJECT_ID(N'[GroupUserMap]'))
ALTER TABLE [GroupUserMap]  WITH NOCHECK ADD  CONSTRAINT [FK_GroupUserMap_User] FOREIGN KEY([UserInfoKey])
REFERENCES [UserInfo] ([UserInfoKey])

Select all Open in new window

It is taking an inordinate amount of time to do 6 million rows.  Is there a way top improve this performance?

The SQL SERVER 2012 installation is on a virtual server which I have no administrative rights to and the customer has fairly limited IT resources too.