Você precisa para indexar colunas de chave estrangeira? Não, absolutamente não.
Você deve indexar colunas de chave estrangeira? Quase certamente. Como você descobriu, as colunas Foreign Key são usadas com frequência em SELECTs e JOINs, e, a menos que sejam indexadas, elas podem realmente acabar com seu desempenho.