If your company has particularly deep pockets, you could consider talking to Salesforce's "Customer Success Group" to undertake a "SubscriberKey Migration". What's achieved is essentially they get their DBAs to run some SQL Stored Procedures that update the old SubscriberKeys with corresponding ones from Salesforce CRM. The cost tends to be prohibitive, these days, so most users in your position tend to forego this and go it alone.
The alternative is to delete all your old Contact records and then complete the connection to CRM using Marketing Cloud Connect. Synchronising Contact/Lead/User records using Data Stream will re-establish contacts in your account using their new CRM record Ids.
Without going through SubscriberKey Migration, you'll have to accept some degree of data loss in terms of the historic information held in Marketing Cloud. Many people back up this data using Tracking Extracts or summarise this information prior to Contact Deletion, so that they have a record of when each Subscriber last opened, clicked, bounced etc. More important, however, is to back up statuses of all your Subscribers so that you can ensure that unsubscribed contacts are suppressed from future sends and that records in a Held status are similarly screened from sends moving forward. It all takes a fair bit of planning.