A6 notebook + mechanical pencil are an indispensable part of my travel kit. i always worry that i will lose my phone at some point so important addresses are written there.
pen and paper can be very useful in places with a different language/writing system. there was a time i looked for a specific product that i had a difficulty describing. fortunately, i met a local who can speak english and asked him to write down the local name of the said product. it can be done on the phone but i find that older people are more comfortable writing with a pen and paper.
for everyday, i use my phone s native notes app for quick jots but still carry with me a notebook and pencil.