É uma loucura não ter um índice.
Ajudaria, mas o comprimento da chave de índice só pode ser de 900 bytes.
No entanto, é provável que você já tenha duplicatas porque o potencial para um 2º EXISTS ser executado após o 1º EXISTS, mas antes do 1º INSERT.
A criação do índice informará e, posteriormente, protegerá contra isso.
No entanto, você pode obter erros sob carga pesada.
Minha abordagem favorita para inserções altas/duplicatas baixas é o padrão JFDI. Altamente simultâneo
BEGIN TRY
INSERT etc
END TRY
BEGIN CATCH
IF ERROR_NUMBER() <> 2627
RAISERROR etc
END CATCH
