We introduce a notion of Koszul A-algebra that generalizes Priddy's notion of a Koszul algebra and we use it to construct small A-algebra models for Hochschild cochains. As an application, this yields new techniques for computing free loop space homology algebras of manifolds that are either formal or coformal (over a field or over the integers). We illustrate these techniques in two examples.