When can I recycle my Macbook Air (mid-2013)?
The Frequently asked questions about the Apple Reuse and Recycling Program page says (emphasis mine):

Which products qualify for the Apple Recycling Program?
Any Mac or PC desktop or notebook computer may qualify for reuse. Any Apple-branded product can be recycled for free.

We can infer that it's at Apple's discretion to provide free recycling for specific Apple hardware (or non Apple hardware). There is no fixed time line for product ranges to be eligible for recycling through Apple.
Since the MacBook Air Mid 2013 is not listed in the list of MacBook Air models that can be recycled through Apple (the latest at this point being the Mid 2012 model), your choices now are to sell it to someone else (since it's a recent machine and has a lot of value left) or recycle it for free through Sims Recycling Solutions (which means you get nothing for the Mac, as opposed to the standard process where Apple evaluates the value of the Mac and sends you a gift card if it has any value).

Recycle it for free.
You can still recycle it by calling Sims Recycling Solutions at 800-966-4135
for a free shipping label and packaging instructions.