Secure Neural Network Inference (SNNI) protocols enable privacy-preserving inference by ensuring the confidentiality of inputs, model weights, and outputs. However, large neural networks, particularly Transformers, face significant challenges in SNNI due to high computational costs and slow execution, as these networks are typically optimized for accuracy rather than secure inference speed. We present COLIBRI, a novel approach that optimizes neural networks for efficient SNNI using Neural Architecture Search (NAS). Unlike prior methods, COLIBRI directly incorporates SNNI execution time as an optimization objective, leveraging a prediction model to estimate execution time without repeatedly running costly SNNI protocols during NAS. Our results on Cityscapes, a complex image segmentation task, show that COLIBRI reduces SNNI execution time by 26–33% while maintaining accuracy, marking a significant advancement in secure AI deployment.