O tamanho da senha não é tão importante; desde que esteja acima de um certo limite, a complexidade é o que mais importa. Você diz que precisa de alta segurança, então vou recomendar que use algo como um fob RSA em combinação com uma senha.
Por quantas vezes mudá-lo, isso depende realmente. Aplicar uma alteração de senha é um nível de proteção contra uma senha comprometida que ainda não foi usada. Mude com muita freqüência e você só vai incomodar os usuários (e aumentar o risco deles escreverem em algum lugar), mudar com pouca frequência e perder essa proteção. Pode-se argumentar que é um benefício duvidoso.
Mais eficaz contra tentativas de violação de força bruta é alguma forma de bloqueio de conta. Bloquear uma conta por até 30 segundos após 3 senhas incorretas sucessivas interromperá um ataque de força bruta morto em seu rastro.
Fale mais sobre o sistema. É interno ou externo? Quão sensíveis são os dados? Esses são fatores que determinarão se alguma recomendação é excessiva (ou insuficiente).