SELECT COUNT(*) FROM - перебрать все строки.
SELECT COUNT(id) FROM - перебрать все строки, в которых указанное поле (в данном случае id) имеет значение отличное от NULL.
Что использовать - вопрос производительности и потребностей. В случае с primary key, это больше вопрос производительности, которая будет зависеть от конкретной СУБД.