Embedded memories occupy increasingly greater portion of SoC area, significantly affecting system performance metrics such as speed and power. The adverse effects of variation, that is accompanying technology scaling, is however making design of these high density memories increasingly challenging. The speed and power consumption of memories is greatly affected by the technique employed to generate timing signals, specifically the sense-amplifier enable (SAE) signal. A BIST based post-silicon tunable approach is known to provide the best tracking with process variation with minimum margins. This paper proposes an improved tuning algorithm that utilizes random-sampling to achieve faster tuning. The algorithm also enables increased utilization of redundancy repair infrastructure to further lower power consumption and improve access speeds.