Yes, wedi is one of those things that doesn't really translate all that neatly into English. It always denotes a 'past' thing, but as you have found, 'being tired' in English is 'being been tired' in Welsh! And just to confuse things further, it's not the only way to say 'I'm tired' (plenty of other ways can be found by looking up 'tired' in the online Geiriadur Academi), although it is probably the most common. As Karla and Netmouse said, thinking of it as a kind of 'after' can help.
While we're on all things tiring (!) -
blino = to tire
blinder = tiredness
blinedig / wedi blino = tired
blinderus = tiring / tiresome
but they can also overlap (e.g. blinedig can also mean tiring).