É necessário colocar static tanto no protótipo da função quanto em sua implementação (tudo isso no arquivo .c), ou colocar só o protótipo como static ja é o suficiente?
Os dois protótipos devem ser iguais. Experimente compilar escrevendo uma função com o static e outra sem.
E outra coisa. Como a função só está sendo declarada no arquivo .c, e não no .h, essa função ja não seria "invisivel" para os outros arquivos?
Não, essa função poderia ser usada por outros programas/arquivos. Para isto bastaria colocarmos, digamos, no arquivo do meu-programa.c o protótipo da função (para não dar erro de sintaxe) e mandar "linkar" e com ".o" que contém o código da função. Para brincar um pouco, faça uns testes bem pequenos, por exemplo coloque em um arquivo uma função de protótipo void oi(); que só imprime um "oi" e compile gerando o .o (gcc -c). Depois em um outro arquivo contendo o main use essa função (precisa colocar o protótipo da função oi nesse arquivo). Repita o mesmo teste colocando o static no protótipo da oi.