Phasing out bills is definitely feasible. Bills usually pass through a bank fairly often, at which point they can be removed from circulation. In general banknotes have their design changed every 10-20 years, and very old banknotes are no longer legal tender (though they can sometimes be exchanged at the central bank). A regular bank won't accept a deprecated banknote.

The ECB is currently phasing out 500s, first by removing those it can get its hands on from circulation, and after a few years by declaring the rest no longer legal tender.