The advancement of technology has resulted in a substantial rise in the number of computing devices and the volume of data being transmitted over networks. The need for fast and secure data encryption has become imperative in response to the increase in data transmission and computing devices. In our previous work, we presented a Fisher-Yates Shuffling (FYS) based image encryption algorithm with a timeout feature that ensures improved security and privacy, regardless of key size. However, the implementation was sequential, and it did not fully utilize the multi-core architecture available on modern computer systems. Therefore, this paper seeks to optimize the FYS-based image encryption algorithm’s performance by parallelizing it on a CPU, with the aim of improving its speed without compromising its security and privacy features. The use of Joblib and multithreading are employed to generate the SHA keys, with a quad-core processor with eight logical processors utilized for the research. The parallelization approach has been tested over thousands of images and has been shown to improve the encryption speed by 2 to 5 times compared to the FYS-based image encryption algorithm. The results demonstrate that using CPU parallelization significantly increases the performance of the FYS-based image encryption algorithm.