I assume you always want EntityId to be the primary key, so replacing it by a composite key is not an option (if only because composite keys are far more complicated to work with and because it is not very sensible to have primary keys that also have meaning in the business logic).
The least you should do is create a unique key on both fields in the database and specifically check for unique key violation exceptions when saving changes.
Additionally you could (should) check for unique values before saving changes. The best way to do that is by an Any() query, because it minimizes the amount of transferred data:
if (context.Entities.Any(e => e.FirstColumn == value1
&& e.SecondColumn == value2))
{
// deal with duplicate values here.
}
Beware that this check alone is never enough. There is always some latency between the check and the actual commit, so you'll always need the unique constraint + exception handling.