For a long time now, officially Ni-Cads should have no longer been made due to the environmentally damaging cadmium content, so I've no idea of the quality of what is available.
These people can recell your battery for you, and
these people can supply cells for you to do it yourself.
I don't know the internal construction of the Yamaha battery, but it shouldn't be too difficult to follow the existing pack layout and construction. If you need any specific advice on soldering the connections etc once you know what's necessary, obviously we'll help.