I've found that traveling and discovering new things make time seem to pass slower because I have a lot of memories of those new places. On the other hand when I'm in a routine and keep doing the same thing everyday, it feels that time passes slower at the moment (because I'm bored) but looking back then time seems to have flown by

Exactly my experience and fits with my idea of how time is perceived in general. Ask a young child what they did this last week and they can likely rattle off a whole bunch of things that they've learned/experienced/discovered for the first time - a lot of 'memory milestones'. Ask your average adult and you'll often just get "same same" - no new 'memory milestones' because the week was pretty much just a repeat of a regular routine.

As for how it feels at the time. There's a lot of truth in the sayings "time flies when you're having fun" and "a watched pot never boils".

It's a paradox.