Os certificados tipo x.509 são usados para verificar assinatura de módulos, programas e o próprio kernel (caso use o secure boot). Se vc não usa secure boot e nem essas ferramentas de segurança avançada do sistema, isso passa a ser apenas uma mensagem de aviso na inicialização.
Mas se vc usa essas ferramentas avançada de verificação de integridade do sistema (integrity check), o sistema não iria iniciar.
Quase certeza que não é isso que atrasa a inicialização. Pra ver se a inicialização está ocorrendo em tempo normal:
Usa SSD ou HDD?
Qual a saída do comando ? systemd-analyze