Security is an important issue, especially in today’s technologically advanced society. Global System for Mobile Communications (GSM) is a world-wide standard for digital wireless communication. GSM uses A5/1 stream cipher in order to provide privacy on air communication. This paper introduce new improvements to the A5/1 stream cipher in order overcome the weakness that appear in clocking mechanism that used in A5/1 stream cipher. New S-box generation is proposed to increase the efficient for A5/1 majority function and improve randomness features. The randomness results confirm that the output bit-stream generated by the proposed stream cipher has improved the randomness performance.