There's a perfectly fine mutual authentication mechanism provided by the krb_ap_rep message in the Kerberos protocol. Use that; it has the same number of messages as your current scheme. If you pass in the mutual flag to krb5_mk_req you should get an ap_rep out of krb5_rd_req.