You can order it directly from Thong Sia in KL.
Part No for the Strap is R03C011J9.

http://www.thongsia.com.my/en/seiko/store/dealer/

Go check the authorized dealers for KK, Sabah. I find it hard to believe not a single one of them don't stock nor replace rechargeable batteries for solar powered watches.

Nice Seiko JDM; SAGA125. Atomic Radio Wave Signal is not available in Malaysia, where was your location when you found it cannot receive radio signal? Have you tried calling Thong Sia instead? Most if not all of their staff are old timers and they do things the old fashion way. Call their service center and give the caseback number of the watch (8B54-0AP0), describe the problem and hear what solution they can offer you.

You want a service center with a better form of communication? Get an Orient. You can send inquires to AD Time Orient SC via WhatsApp with prompt replies.

SRP613K1

Seiko wants you to buy a Grand Seiko for perfect alignment.