Damn right it's hard to climb! I think in terms of gear inches - which has a pedigree going back to 'ordinaries' aka penny farthings - in which you travel forwards pi * number of inches, which was originally the diameter of the front wheel. Anyhow, I'd consider a gear of 40" suitable for most climbing (at my age and weight I'm now looking at 30" or so!). Your lowest gear, calculated as teeth on chainring * nominal diameter of wheel / number of teeth on rear sprocket, is 40 * 27 / 23 = 47 (rounded to nearest integer). By the same calculation, your top gear is 117", plenty high enough not to spin out in normal riding.
Your options are to fit a smaller chainring, fit a cassette with more teeth on the largest sprocket, or as you suggest, both.
Firstly, it may be possible to find a solution with your existing chainset; the obvious first suggestion would be a different cassette. Is it Campag, Shimano or something more exotic? Working on the assumption that it's Shimano, you could fit a straight 8-speed replacement HG50 13-26, to give a new low gear of 41.5.
Other options include 11-28, 11-30 and 11-32, BUT you'd probably never use the two smallest sprockets on these, and might well need a longer rear derailleur.
Next to consider is your chainset and what the bcd (bolt circle diameter) is. Measure (fairly accurately!) the distance between the centre of two adjoining bolts: if this is 76.4mm you have 130 bcd and can swap the 40 for a 38 tooth and a worthwhile reduction in bottom gear, if it's 79.4mm you have 135 bcd and could only reduce to a 39 tooth, scarcely worthwhile. Maybe time to think about a compact? Try the 13-26 cassette first, though.
Do you have a square taper bottom bracket? An "upgrade" to this month's latest flavour would require you to replace this with one which is likely to wear more quickly.
While I'm denigrating "upgrades", can I also suggest that an 11-speed cassette might not fit your hub? Nowt wrong with 8 speed!!!!!!