Air travel wasn't provided by the government before deregulation. The airlines have always been private companies. They were heavily regulated and run as public utility. Deregulation increased competition but nothing was privatized, the CAB was eliminated.

Air travel is also not privatized these days. The airports are nearly all owned by government entities.