In view that authentication has made a significant determinant in handover delay, this paper presents a fast authentication mechanism for mobile stations roaming within a WiMAX-WLAN interconnected environment. Incorporating a key reuse design that prevents repeated transactions at a remote server, our mechanism distributes security contexts ahead of handover to a local trusted key holder which manages several sites. A target site, upon receiving a mobile station, retrieves the contexts locally for authentication purpose and thus completes handover efficiently. While employing a target prediction algorithm as an option, our mechanism distributes the contexts to target candidates as dictated, which further improves handover performance if target prediction hits and maintains its advantage even in a miss. In addition, the handover optimization design specified in WiMAX is extended to support WiFi-to-WiMAX handovers. We reason that the proposed mechanism does not compromise the system in any sense as well. Analytical and simulation results show that, despite key pre-distribution misses, our mechanism leads to marked improvement over counterpart schemes in terms of handover delay and packet loss, meeting delay-sensitive application requirements.