Just don’t use Entity Framework in this case. Just use a stored procedure (how to depends on the version/approach you use with EF, you might will have to extend your DbContext or add a mapping from the entity model).
If you’re using SQL Server, then in your store procedure, do use the MERGE command that efficiently does exactly what you need: insert if it doesn’t exist, or update if it does. Everything in a single, efficient SQL query.