In this paper, we designed a new hyperchaotic two-dimensional map with wide distribution and two large positive Lyapunov exponents. Then, we used it to construct a new randomized bit-level chaotic image encryption algorithm with the proposed hyperchaotic map as the source of randomization for permutation and diffusion. The input image is randomized by appending an extra random row and an additional random column to it. Then, the whole permutation and diffusion process are randomized by relating the parameters of the hyperchaotic mapping dependent on the hash value of the randomized image. In the permutation step, the randomized image is split into binary images, and then each binary image is randomly and independently permuted. Then, the permuted binary images are combined, and diffusion is applied to each pixel. Various security experiments are designed to assess the performance of the proposed encryption algorithm, including entropy analysis, histogram analysis, key-space analysis, the pixel-level and the bit-level correlation analysis, and differential attacks as well as key-sensitivity and randomization analysis. According to these experiments, the proposed algorithm shows an excellent security performance compared to several recent image encryption algorithms. Moreover, the proposed encryption algorithm is robust against data loss and noise attacks. Finally, the running time of the proposed algorithm is smaller compared to several recent algorithms.