A behavioral authentication (BA) system leverages the behavioral characteristics of users to verify their identity claims through a verification algorithm. A verification algorithm can be created by employing a machine learning (ML) classifier trained on user profiles, which improves overall system efficiency. However, similar to other ML systems, ML-based BA classifiers are vulnerable to privacy attacks that can leak sensitive behavioral data. To protect behavioral data, we propose a non-cryptographic approach suitable for low-computation devices. Before sharing the profiles with the verifier, users apply a random projection (RP) transformation to their behavioral profiles. This transformation ensures the correctness and security properties of the BA systems, as RP can preserve the Euclidean distances between vectors in a metric space with high probability. Our approach also satisfies key privacy-preserving properties of authentication systems, including renewability, unlinkability, and irreversibility. Extensive experiments on two behavioral datasets, combined with comprehensive security and privacy evaluations, demonstrate the effectiveness of our method. Moreover, our approach is general and can be applied to other BA systems.