Tente alterar o índice para ambas as colunas (status, id)

A meu ver, você não tem nenhum índice no id

O padrão ANSI (procure por "Scalar expressions 125 ") afirma que COUNT(*) forneça a contagem de linhas de uma tabela:ela deve ser otimizada desde o início.

É por isso que COUNT(*) é muito mais rápido que COUNT(id) . COUNT(*) pode usar o status índice. COUNT(id) não usará este índice e não há outro índice válido

O que é o índice clusterizado e o que é o PK? Você tem ambos (mesmo que o mesmo índice), certo?