C# Performance is slow on list comparisons using LINQ

Creating a HashSet will probably solve your problems:

    var mobile = new HashSet<string>(duplicates.Select(x => x.MobilePhone));
    var telephone2 = new HashSet<string>(duplicates.Select(x => x.Telephone2));

There are other performance improvements you can make, but they'll be micro-optimizations compared to avoiding iterating over 5 million items for each number you check.

You can use Enumerable.Except.
Enumerable.Except uses HashSet internally to improve lookup performance. You want to use the overload which allows to pass in a custom IEqualityComparer as an argument.

Also note that ToList() is a LINQ query finalizer. Means that ToList() executes the LINQ expression immediately - which results in a complete iteration over the collection. LINQ's power is that queries are executed deferred, which improves the performance significantly. All sub-queries (whether chained or split up in separate statements) are merged into one single iteration using yield return internally:

Good performance:

// Instead of two iterations, LINQ will defer both 
// iterations and merge them into a single iteration
var filtered = collection.Where(); // Deferred iteration #1
var projected = filtered.Select(); // Deferred iteration #2
var results = projected.ToList(); // Results in one single iteration

Bad performance:

// LINQ will execute each iteration immediately
// resulting in two complete iterations
var filtered = collection.Where().ToList(); // Executed iteration #1
var projected = filtered.Select().ToList(); // Executed iteration #2

You should avoid to call a finalizer before you actually want to execute the query to significantly improve the performance:

// Executes deferred
var mobile = duplicates.Select(x => x.MobilePhone);

Instead of:

// Executes immediately
var mobile = duplicates.Select(x => x.MobilePhone).ToList();

Also note that each Enumerable.Contains executes a separate iteration. Contains is a finalizer and will execute immediately:

return model.Contacts
  .Where(y => 
    !mobile.Contains(y.Phonenumber.ToPhoneNumber()) // Iteration #1
      && !telephone2.Contains(y.Phonenumber.ToPhoneNumber()) // Iteration #2
      && !mobile.Contains(y.Phonenumber2.ToPhoneNumber()) // Iteration #3
      && !telephone2.Contains(y.Phonenumber2.ToPhoneNumber())) // Iteration #4
  .ToList(); // Iteraion #5

Worst case iterates over n elements * 4 Enumerable.Contains * 5*10^6 reference elements in mobile and telephone2 - only for comparison!

Enumerable.Except

ContactEqualityComparer.cs

class ContactEqualityComparer : IEqualityComparer<Contact>
{
  public bool Equals(Contact contact1, Contact contact2)
  {
    if (ReferenceEquals(contact1, contact2))      
      return true;
    else if (ReferenceEquals(contact1, null) || ReferenceEquals(contact2, null))
      return false;
    else if (contact1.MobileNumber.Equals(contact2.MobileNumber, StringComparoison.OrdinalIgnoreCase) 
      && contact1.PhoneNumber2.Equals(contact2.PhoneNumber2, StringComparer.OrdinalIgnoreCase))
      return true;
    else
      return false;
  }

  // Will be used by Enumerable.Except to generate item keys 
  // for the lookup table
  public int GetHashCode(Contact contact)
  {
    unchecked
    {
      return ((contact.MobileNumber != null 
        ? contact.MobileNumber.GetHashCode() 
        : 0) * 397) ^ (contact.PhoneNumber2 != null 
          ? contact.PhoneNumber2.GetHashCode() 
          : 0);
    }
  }
}

Contact.cs
Consider to use two properties for each data: one property for computations and one for display e.g. MobileNumber and MobileNumberDisplay. The computation properties should be numeric.

public class Contact : IEqualityComparer<Contact>
{
  private string mobileNumber;
  public string MobileNumber
  {
    get => this.mobileNumber;
    set => this.mobileNumber = value.ToPhoneNumber();
  }

  private string phoneNumber2;
  public string PhoneNumber2 
  { 
    get => this.phoneNumber2; 
    set => this.phoneNumber2 = value.ToPhoneNumber();
  }
    
  public string ToPhoneNumber(string phoneNumber)
  {
    if (phoneNumber == null || phoneNumber == string.Empty)
        return string.Empty;

    return phoneNumber.Replace("(", "").Replace(")", "")
        .Replace(" ", "").Replace("-", "");
  }
}

Example

private List<Contact> GetNewContactsNotFoundInCrm(ContactPostModel model) 
{    
  List<Contact> duplicates = GetAllNumbers();

  return model.Contacts
    .Except(duplicates, new ContactEqualityComparer())
    .ToList(); 
}

One good option here is to try removing the need for the phone number conversions (call to ToPhoneNumber method) over each iteration step, by making both regular numbers (the one you convert ToPhoneNumber), telephone number and mobile numbers and telephone2 numbers to compared by the same format.

The other thing to improve over the query is to cach the calls for mobile and telephone2 numbers. You can move their calculation outside of the GetNewContactsNotFoundInCrm method and acquire only when there is a new change in data.

Finally, consider using HashSet for removing the need to have duplicates and make fast comparisons.

Side note:

If you are dealing with the database elements, consider moving this logic to SQL Stored Procedure.