They're not really comparable; Clojure protocols are a more flexible (runtime-extensible, for instance) notion of a (non-hierarchical) interface, and records / deftypes are just straight-up Java classes, with records having in addition nice map-style access to members.

I haven't used Typed Clojure, so I can't speak to that, but if you want to do type-level programming Clojure is probably not your weapon of choice.