This paper presents the Random Key Optimization (RKO), a versatile and efficient probabilistic local search method for combinatorial optimization problems. RKO uses the concept of random keys to encode solutions into random key vectors and decode them into feasible solutions via a problem-specific decoder. The RKO framework can combine various classical metaheuristic techniques, each operating independently or in parallel, and sharing solutions through an elite solution pool. This modular approach allows the application of various metaheuristic techniques, including simulated annealing, iterative local search, and greedy random adaptive search procedures. The efficiency of the RKO framework, implemented in C++ and publicly available (GitHub repository: github.com/RKO-solver), is demonstrated by applying it to three NP-hard combinatorial optimization problems: the alpha-neighborhood p-median problem, the hub-location tree problem, and the node-capacity-constrained graph partitioning problem. The results demonstrate the framework's ability to generate high-quality solutions across a wide range of problem domains, highlighting its potential as a powerful tool for combinatorial optimization.